OJ Board

Code: Select all

#include<bits/stdc++.h>
using namespace std;
 int n,profit1,profit2;
  int dpi[101][101],cost[1000],weight[1000],cap;
int dp(int i,int w)
{
    if(i==n+1)
        return 0;
        if(dpi[i][w]!=-1)
            return dpi[i][w];
            int profit1=0,profit2=0;
    if(w+weight[i]<=cap)
        profit1=cost[i]+dp(i+1,w+weight[i]);
        profit2=dp(i+1,w);
        dpi[i][w]=max(profit1,profit2);
        return dpi[i][w];
}
int main()
{
    int t;
scanf("%d",&t);
for(int m=1;m<=t;m++)
{
    int sum=0;
    scanf("%d ",&n);
   for(int i=1;i<=n;i++)
   {
       scanf("%d %d",&cost[i],&weight[i]);
   }
    int g;
    scanf("%d",&g);
    for(int k=0;k<g;k++)
    {
         memset(dpi,-1,sizeof(dpi));
        scanf("%d",&cap);
    sum+=dp(1,0);
    }
    printf("%d\n",sum);
}

    return 0;
}

Code: Select all

#include <stdio.h>

int N, dp[1005][35], v[1005], w[1005], hist[105];

int solve(int i, int capital){
    int left, right;
    if(i == N)
        return 0;
    if(dp[i+1][capital] >= 0) {
        return dp[i+1][capital];
    }
    left = solve(i+1, capital);
    if(capital >= w[i]) {
        right = v[i] + solve(i+1, capital - w[i]);
    } else {
        right = 0;
    }
    return dp[i+1][capital] = (left > right) ? left : right;
}

int main() {
    int tC, per, sum, i, j, k, person;
    scanf("%d", &tC);
    while(tC--) {
        scanf("%d", &N);
        for(i = 0; i < N; i++){
            scanf("%d %d", &v[i], &w[i]);
        }
        scanf("%d", &per);
        sum = 0;

        for(i = 0; i < 1005; i++){
            hist[i] = -1;
        }

        for(i = 0; i < per; i++){
            scanf("%d", &person);
            if(hist[person] < 0) {
                for(j = 0; j < 1005; j++){
                    for(k = 0; k < 35; k++){
                        dp[j][k] = -1;
                    }
                }
                hist[person] = solve(0, person);
            }
            sum+= hist[person];
        }

        printf("%d\n", sum);
    }
    return 0;
}