Problem E: Papercut
Description
现在桌面上有一张矩形纸，上边有n×m个格子，每个格子有一个数字。 每张矩形纸可以算出一个数值F，F是由纸张里任意两个不同的格子里的数字相乘之和。如果该纸只有一个格子，那么F=0。
剪纸规则是：
1、沿格子边缘一直剪成两个矩形纸，每张纸里必须有数字。
2、每次剪纸在桌面上任意选一张矩形纸，进行1操作，再把剪出来的两张纸放到桌面。
现在你可以对桌面上的纸最多剪k次，问最后桌面上所有矩形纸的F值之和最小是多少？
1 ≤ n ≤ 10
1 ≤ m ≤ 10
1 ≤ k ≤ 50
Input
第一行：3个整数n, m, k
接下来n行：每行m个正整数，范围在[1,10]，第i行第j个数表示当前桌面那张矩形纸里边第i行第j个格子里的数字。
Output
一个整数。代表最小F值和。
Sample Input
Sample Input #1
Sample Input #2
4 4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
10 10 5
4 2 3 5 6 10 1 6 5 8
3 6 9 1 7 10 7 10 8 1
7 8 3 3 2 5 9 9 8 2
5 5 9 9 3 10 2 9 10 2
1 1 6 7 6 8 3 9 6 8
7 1 2 5 3 2 3 7 8 10
10 9 8 9 7 8 10 7 3 9
6 3 6 2 1 7 10 6 7 2
2 4 8 4 5 9 10 5 9 10
7 4 3 2 4 9 9 9 8 1
Sample Output
Sample Output #1
Sample Output #2
18
26612
Hint
Sample 1说明： 按照下面方式剪纸4次
1 1 1 1
-------------
1 | 1 | 1 | 1
| | |
1 | 1 | 1 | 1
| | |
1 | 1 | 1 | 1
得到6+3+3+3+3=18
记忆化DP
#include<iostream>
using namespace std;
int dp[11][11][11][11][55],fv[105],paper[15][15];
int dfs(int sr,int sc,int er,int ec,int k)
{
if(sr==er && sc==ec && k)
return -1;
int i,j,a,b,n,ans;
if(k==0){
for(ans=n=0,i=sr;i<=er;i++)
for(j=sc;j<=ec;j++)
fv[n++]=paper[i][j];
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
ans+=fv[i]*fv[j];
return dp[sr][sc][er][ec][k]=ans;
}
if(dp[sr][sc][er][ec][k]!=-1)
return dp[sr][sc][er][ec][k];
for(ans=INT_MAX,i=sc+1;i<=ec;i++)
for(j=0;j<k;j++){
a=dfs(sr,sc,er,i-1,j);
if(a>=ans || a==-1)
continue;
b=dfs(sr,i,er,ec,k-1-j);
if(a>=0 && b>=0 && a+b<ans)
ans=a+b;
}
for(i=sr+1;i<=er;i++)
for(j=0;j<k;j++){
a=dfs(sr,sc,i-1,ec,j);
if(a>=ans || a==-1)
continue;
b=dfs(i,sc,er,ec,k-1-j);
if(a>=0 && b>=0 && a+b<ans)
ans=a+b;
}
return dp[sr][sc][er][ec][k]=ans;
}
int main(){
int i,j,n,m,k;
while(cin>>n>>m>>k){
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin>>paper[i][j];
memset(dp,-1,sizeof(dp));
cout<<dfs(0,0,n-1,m-1,k)<<endl;
}
return 0;
}