QAQ QAQ萌新一脸懵逼 30分后面全部TLE
C++
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100+5;
int v[maxn],w[maxn],m;
int dp(int i,int c,int t){
if(i==m+1||t<=0) return 0;
int ans=0;
if(c==1) if(t-v[i]>=0) ans=max(dp(i+1,0,t-v[i]),dp(i+1,1,t-v[i]))+w[i];
if(c==0) ans=max(dp(i+1,0,t),dp(i+1,1,t));
return ans;
}
int main(){
// freopen("P1104.in","r",stdin);
int t;
scanf("%d%d",&t,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&v[i],&w[i]);
printf("%d\n",max(dp(1,0,t),dp(1,1,t)));
return 0;
}
1 条评论
-
Fan_T LV 7 @ 2016-09-20 12:47:32
貌似这样可以了QAQ
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=105;
int v[maxn],w[maxn],d[maxn][maxn*10];
int main(){
//freopen("P1104.in","r",stdin);
int t,m;
scanf("%d%d",&t,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=m;i>0;i--)
for(int j=0;j<=t;j++){
d[i][j]=d[i+1][j];
if(j>=v[i]) d[i][j]=max(d[i][j],d[i+1][j-v[i]]+w[i]);
}
printf("%d\n",d[1][t]);
return 0;
}
- 1
