单调队列
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int n,m; int i,j,k; int p[105],h[105],c[105]; int dp[2500]; void MPqueue(int dp[], int SumValue, int value, int n, int weight) { if(n==1) { for (j =SumValue;j>=value;j--) dp[j]=max(dp[j],dp[j-value]+weight); } else if(n*value>=SumValue-value+1) { for(j=value;j<=SumValue;j++) dp[j]=max(dp[j],dp[j-value]+weight); } else { int Q1[2500],Q2[2500]; int Head1,Head2,Tail1,Tail2; int Count; int t; for(j=0;j<value;j++) { Head1=Tail1=0; Head2=Tail2=0; Count=0; for(k=j;k<=SumValue;k+=value) { if (Tail1-Head1 ==n+1) { if (Q2[Head2+1]==Q1[Head1+1]) Head2++; Head1++; } t=dp[k]-Count*weight; Q1[++Tail1]=t; while(Head2<Tail2&&Q2[Tail2]<t) Tail2--; Q2[++Tail2]=t; dp[k]=Q2[Head2+1]+Count*weight; Count++; } } } } int main() { int C; scanf("%d",&C); while(C--) { scanf("%d %d",&n,&m); int count=1; memset(dp,0,sizeof(dp)); for(i=1;i<=m;i++) { scanf("%d %d %d",&p[i],&h[i],&c[i]); } for(i=1;i<=m;i++) { MPqueue(dp,n,p[i],c[i],h[i]); } printf("%d\n",dp[n]); } return 0; }二进制
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int n,m; int i,j,k; int p[105],h[105],c[105]; int dp[2500]; void ZeroOne(int value,int weight) { for(k=n;k>=value;k--) dp[k]=max(dp[k],dp[k-value]+weight); } void Multiply() { for(j=1;j<=c[i];j<<=1) { c[i]-=j; ZeroOne(j*p[i],j*h[i]); } ZeroOne(c[i]*p[i],c[i]*h[i]); } int main() { int C; scanf("%d",&C); while(C--) { scanf("%d %d",&n,&m); int count=1; memset(dp,0,sizeof(dp)); for(i=1;i<=m;i++) { scanf("%d %d %d",&p[i],&h[i],&c[i]); } for(i=1;i<=m;i++) { Multiply(); } printf("%d\n",dp[n]); } return 0; }