题解 P4878 【[IOI2009]葡萄干raisins】

SuperJvRuo

2018-08-31 15:29:11

Solution

此题竟然放在了D1T4的位置,不知组题人有何居心。完全是一道NOIP普及组题。 不难想到$O(n^5)$的dp解法,状态数$O(n^4)$,转移$O(n)$。$f[i][j][k][l]$表示左上角为$u$行$l$列,右下角为$d$行$r$列的子矩形的结果。对这个子矩形切一刀有$O(n)$种切法,因此转移为$O(n)$。预处理出前缀和,写一发记忆化搜索~~开启o2优化~~就过了。 ``` #include<cstdio> #include<climits> #include<algorithm> #define LL long long int sum[55][55]; LL f[55][55][55][55]; LL dfs(int u,int d,int l,int r) { if(f[u][d][l][r]) return f[u][d][l][r]; else if(u==d&&l==r) { //递归边界,如果只剩一小块,返回0 return 0; } else { f[u][d][l][r]=LLONG_MAX; LL cut=sum[d][r]-sum[d][l-1]-sum[u-1][r]+sum[u-1][l-1];//这一大块上的总数 for(int i=l;i<r;++i) { f[u][d][l][r]=std::min(dfs(u,d,l,i)+dfs(u,d,i+1,r),f[u][d][l][r]); } //竖着切 for(int i=u;i<d;++i) { f[u][d][l][r]=std::min(dfs(u,i,l,r)+dfs(i+1,d,l,r),f[u][d][l][r]); } //横着切 f[u][d][l][r]+=cut; return f[u][d][l][r]; } } int main() { int n,m; scanf("%d%d",&n,&m); int temp; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { scanf("%d",&temp); sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+temp; }//预处理前缀和 } printf("%lld",dfs(1,n,1,m)); return 0; } ```