先写普通dp，得分70，
写的时候要注意dp的顺序，
如果原来有值，不可以直接覆盖，要判断，
如果上一次可行，这一次可以不改变，要把状态转移过来
memset（128）就是刷新成-inf
无优化dp：
//先写一遍普通dp练手 #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define ll long long using namespace std; int n,mxp,w; const int N=2003; int in[N],out[N]; ll a[N],b[N],f[N][N]; inline int read() { int x=0;char c=getchar(); while(c<‘0‘ || c>‘9‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-‘0‘,c=getchar(); return x; } int main() { n=read(),mxp=read(),w=read(); memset(f,128,sizeof(f)); for(int i=1;i<=n;i++) { a[i]=read(),b[i]=read(),in[i]=read(),out[i]=read(); for(int j=0;j<=in[i] && j<=mxp ;j++) f[i][j]=-1*a[i]*j; for(int j=0;j<=mxp;j++) f[i][j]=max(f[i][j],f[i-1][j]); if(i>w+1) for(int j=0;j<=mxp;j++) { for(int k=1;k<=in[i] && j>=k ;k++) f[i][j]=max(f[i][j],f[i-w-1][j-k] -a[i]*k); for(int k=1;k<=out[i] && j+k<=mxp ;k++) f[i][j]=max(f[i][j],f[i-w-1][j+k] +b[i]*k); } } printf("%d\n",f[n][0]); return 0; }
考虑优化,
? 买入时：
? f[i][j]= f[i-w-1][k] -a[i] * (j-k) k<=j && k>=j-in[i]
? = f[i-w-1][k] +a[i]*k - a[i] * j
?我们发现，对于每一个i，都枚举了j*k，
但是 j和k 其实是可以分离的，所以其实可以降成 j+k，然后用单调队列优化，
先处理k，再给j赋值
卖出时
f[i][j]= f[i-w-1][k] +b[i]*(k-j) k<=mxp && k<=j+out[i] && k>j
= f[i-w-1][k] +b[i]*k -b[i]*j
所以买入的时候，j,k从小到大，把最可能出队的小的k，放在队头，
卖出的时候，j,k从大到小。
//先写一遍普通dp练手 #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; int n,mxp,w; const int N=2003; int in[N],out[N]; ll a[N],b[N],f[N][N]; inline int read() { int x=0;char c=getchar(); while(c<‘0‘ || c>‘9‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-‘0‘,c=getchar(); return x; } struct node {int v,pos;}; deque <node> q; int main() { n=read(),mxp=read(),w=read(); memset(f,128,sizeof(f)); int inf=f[0][0]; for(int i=1;i<=n;i++) { a[i]=read(),b[i]=read(),in[i]=read(),out[i]=read(); for(int j=0;j<=in[i] && j<=mxp ;j++) f[i][j]=-1*a[i]*j; for(int j=0;j<=mxp;j++) f[i][j]=max(f[i][j],f[i-1][j]); if(i>w+1) { q.clear() ; int pre=i-w-1; for(int j=0;j<=mxp;j++)//等下想怎么去掉无用状态 { if(!q.empty() && q.front() .pos < j-in[i]) q.pop_front() ; int val=f[pre][j] +a[i]*j; while(!q.empty() && q.back() .v <=val) q.pop_back() ; q.push_back((node){val,j}); f[i][j]=max(f[i][j],q.front() .v-a[i]*j); } q.clear() ; for(int j=mxp;~j;j--) { if(!q.empty() && q.front() .pos > j+out[i]) q.pop_front() ; int val=f[pre][j] +b[i]*j; while(!q.empty() && q.back() .v <=val) q.pop_back() ; q.push_back((node){val,j}); f[i][j]=max(f[i][j],q.front() .v-b[i]*j); } } } printf("%d\n",f[n][0]); return 0; }
原文：https://www.cnblogs.com/xwww666666/p/11694307.html