首页 > 分享 > 题解 P1854 花店橱窗布置

题解 P1854 花店橱窗布置

花匠小妙招
2024-09-15 07:28

把二维压成一维的DP了解一下。。。

传送门

（以纪念神经兮兮调了两天的一维DP（刷水题谋财害命）以及感谢学长的帮助@ydnhaha）显然我们有二维的dp：f[i][j]代表第i盆花放到第j个位置

for(R i=1;i<=n;i++) for(R j=V-(n-i);j>=i;j--) for(R k=j-1;k>=i-1;k--) if(f[i][j]<f[i-1][k]+w[i][j]) ans[i][j]=k,f[i][j]=f[i-1][k]+w[i][j];

由于只访问上一个状态，我们可以理所应当的把它压掉

注意，需要倒序循环（好吧我的二维的也是倒序的QWQ）

for(R i=1;i<=n;i++) for(R j=V-(n-i);j>=i;j--) { f[j]=0xcfcfcfcf; for(R k=j-1;k>=i-1;k--) if(f[j]<f[k]+w[i][j]) ans[i][j]=k,f[j]=f[k]+w[i][j]; } 时间复杂度不变但是空间小了一些？

AC代码

二维的：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define R register int using namespace std; int n,V,pos=109; int w[110][110],f[110][110],ans[110][110]; inline void print(int i,int j) { if(!i) return ; print(i-1,ans[i][j]); printf("%d ",j); } signed main() { //freopen("testdata.in","r",stdin); memset(f,0xcf,sizeof(f)); scanf("%d%d",&n,&V);f[n][109]=0xcfcfcfcf; for(R i=1;i<=n;i++) for(R j=1;j<=V;j++) scanf("%d",&w[i][j]); for(R i=0;i<=V;i++) f[0][i]=0; for(R i=1;i<=n;i++) for(R j=V-(n-i);j>=i;j--) for(R k=j-1;k>=i-1;k--) if(f[i][j]<f[i-1][k]+w[i][j]) ans[i][j]=k,f[i][j]=f[i-1][k]+w[i][j];//,cout<<i<<" "<<j<<" "<<k<<" "<<f[1][1]<<endl; for(R i=V;i>=n;i--) if(f[n][i]>f[n][pos]) pos=i; printf("%dn",f[n][pos]),print(n,pos); }

一维的：

(其实一维的有点像01背包对吧)

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define R register int using namespace std; int n,V,pos=109; int w[110][110],f[110],ans[110][110]; inline void print(int i,int j) { if(!i) return ; print(i-1,ans[i][j]); printf("%d ",j); } signed main() { //freopen("testdata.in","r",stdin); //memset(f,0xcf,sizeof(f)); scanf("%d%d",&n,&V);f[109]=0xcfcfcfcf; for(R i=1;i<=n;i++) for(R j=1;j<=V;j++) scanf("%d",&w[i][j]); //for(R i=0;i<=V;i++) f[0][i]=0; for(R i=1;i<=n;i++) for(R j=V-(n-i);j>=i;j--) { f[j]=0xcfcfcfcf; for(R k=j-1;k>=i-1;k--) if(f[j]<f[k]+w[i][j]) ans[i][j]=k,f[j]=f[k]+w[i][j];//,cout<<i<<" "<<j<<" "<<k<<" "<<f[1][1]<<endl; } for(R i=V;i>=n;i--) if(f[i]>f[pos]) pos=i; printf("%dn",f[pos]),print(n,pos); }

2019.3.3

转载于:https://www.cnblogs.com/Jackpei/p/10465868.html