类似于背包,但是最后物品可以拆分.另外,因为要求第一次的选择,从后往前进行dp.

代码如下:

#include
   
     #include
    
      #include
     
       using namespace std; #define INF 0x3f3f3f3f typedef struct { int cnt; int w[103],v[103]; }P; P p[55]; int dp[55][550]; int main() { //freopen("in.txt","r",stdin); int n,m; while(scanf("%d%d",&n,&m)!=EOF) { m++; memset(dp,0,sizeof(dp)); for(int i=m;i>=1;i--) { scanf("%d",&p[i].cnt); for(int j=0;j
      
       =0;j--) { for(int k=0;k
       
        =0&&dp[i-1][j-p[i].v[k]]!=-1) { dp[i][j]=max(dp[i][j],dp[i-1][j-p[i].v[k]]+p[i].w[k]*p[i].v[k]); } if(j==p[i].v[k]) ///可以卖任意多张的票 for(int d=p[i].v[k]-1;d>=0;d--) if(dp[i-1][0]!=-1) dp[i][d]=max(dp[i][d],dp[i-1][0]+d*p[i].w[k]); } } } int sum=0; for(int i=0;i<=n;i++) sum=max(dp[m][i],sum); if(m==1) ///m==1的情况需特判 { printf("%d\n",sum); for(int i=0;i