【DP 训练】Cake Slicing, ACM/ICPC Nanjing 2007, UVa1629
傻逼了。。dp[u][d][l][r]里面打错 dp[u][l][d][r]。。然后debug了一天没发现！！
#include<bits/stdc++.h>
using namespace std;
int n,m,k,casecnt;
int a[30][30];
int dp[30][30][30][30];
int sum[30][30];
const int INF = 100000;
int check(int u,int d,int l,int r)
{
int cnt = 0;
cnt+=sum[d][r];
cnt-=sum[u-1][r];
cnt-=sum[d][l-1];
cnt+=sum[u-1][l-1];
return cnt;
}
int dfs(int u,int d,int l,int r)
{
if(dp[u][d][l][r]!=-1)return dp[u][d][l][r];
dp[u][d][l][r] = INF;
int ret = check(u,d,l,r);
if(ret==0)
{
dp[u][d][l][r] = INF;
return INF;
}
else if(ret==1)
{
dp[u][d][l][r] = 0;
return 0;
}
int& ans = dp[u][d][l][r];
for(int i=u;i<d;i++)//横切
{
ret = dfs(u,i,l,r)+dfs(i+1,d,l,r)+r-l+1;
ans = min(ans,ret);
}
for(int i=l;i<r;i++)//竖切
{
ret = dfs(u,d,l,i)+dfs(u,d,i+1,r)+