Problem E: Papercut
Description
現(xiàn)在桌面上有一張矩形紙，上邊有n×m個(gè)格子，每個(gè)格子有一個(gè)數(shù)字。 每張矩形紙可以算出一個(gè)數(shù)值F，F是由紙張里任意兩個(gè)不同的格子里的數(shù)字相乘之和。如果該紙只有一個(gè)格子，那么F=0。
剪紙規(guī)則是：
1、沿格子邊緣一直剪成兩個(gè)矩形紙，每張紙里必須有數(shù)字。
2、每次剪紙?jiān)谧烂嫔先我膺x一張矩形紙，進(jìn)行1操作，再把剪出來(lái)的兩張紙放到桌面。
現(xiàn)在你可以對(duì)桌面上的紙最多剪k次，問(wèn)最后桌面上所有矩形紙的F值之和最小是多少？
1 ≤ n ≤ 10
1 ≤ m ≤ 10
1 ≤ k ≤ 50
Input
第一行：3個(gè)整數(shù)n, m, k
接下來(lái)n行：每行m個(gè)正整數(shù)，范圍在[1,10]，第i行第j個(gè)數(shù)表示當(dāng)前桌面那張矩形紙里邊第i行第j個(gè)格子里的數(shù)字。
Output
一個(gè)整數(shù)。代表最小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說(shuō)明： 按照下面方式剪紙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;
}