资格赛 Problem E

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;
}

posted on 2009-05-10 22:07 极限定律 阅读(1325) 评论(0)  编辑 收藏 引用 所属分类: 腾讯2009程序设计大赛


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(10)

随笔分类

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜