题解 P4878 【[IOI2009]葡萄干raisins】
SuperJvRuo
2018-08-31 15:29:11
此题竟然放在了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;
}
```