BUPT OJ 丁神又去谷歌

/* USER_ID: test#bupt_wcy PROBLEM: 417 SUBMISSION_TIME: 2017-03-10 12:05:45 */ #include<iostream> #include<cstdio> #define MAXSIZE 10002 using namespace std; // DP int n; int a[MAXSIZE]; long long b[MAXSIZE]; // f[i][j]=max(f[i-a[j]][j+1]+b[j],f[i][j+1]); long long f[1001][101]; int main() { int T,t; scanf("%d",&T); while(T--) { scanf("%d %d",&t,&n); for(int j=0;j<n;j++) { scanf("%d %lld",&a[j],&b[j]); } for(int j=0;j<n;j++) f[0][j]=0; for(int i=1;i<=t;i++) for(int j=n-1;j>=0;j--) { if(i-a[j]>=0) f[i][j]=max(f[i-a[j]][j+1]+b[j],f[i][j+1]); else f[i][j]=f[i][j+1]; } cout<<f[t][0]<<endl; } }