矩阵取数问题（dp,高精）

题目描述

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n×mn \times mn×m的矩阵，矩阵中的每个元素ai,ja_{i,j}ai,j均为非负整数。游戏规则如下：

每次取数时须从每行各取走一个元素，共nnn个。经过mmm次后取完矩阵内所有元素；
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值×2i\times 2^i×2i，其中iii表示第iii次取数（从111开始编号）；
游戏结束总得分为mmm次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入输出格式

输入格式：

输入文件包括n+1n+1n+1行：

第111行为两个用空格隔开的整数nnn和mmm。

第2∽n+12\backsim n+12∽n+1行为n×mn \times mn×m矩阵，其中每行有mmm个用单个空格隔开的非负整数。

输出格式：

输出文件仅包含111行，为一个整数，即输入矩阵取数后的最大得分。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

NOIP 2007 提高第三题

数据范围：

60%的数据满足：1≤n,m≤301\le n, m \le 301≤n,m≤30，答案不超过101610^{16}1016
100%的数据满足：1≤n,m≤801\le n, m \le 801≤n,m≤80，0≤ai,j≤10000 \le a_{i,j} \le 10000≤ai,j≤1000

分析：这道题主要是用来练习dp ，没有涉及高精的问题，因此代码是不能AC的，但是也学习了一下dp的思想，在洛谷上能够过六个点。。。

我们用dp[i][j]代表区间变为【i，j】时，获得的最大分数当区间变为[i][j]时，一定是由【i-1，j】或者是[i,j-1]这两个符合条件的方程式中转移过来的，在第m-(j-i)-1次i取走了当前值。。。

因此状态转移方程就是 dp[i][j]=max(dp[i-1][j]+a[t][i-1]*mypow(len),dp[i][j+1]+a[t][j+1]*mypow(len));

在这要注意一下，当区间长度为1时，它是没有办法把最后一个数字取出来的。因此在这里要在重新加上。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define ll unsigned long long

 const int maxn = ;

 ll mypow(int k){

     ll sum=;

     for(int i=; i<=k; i++ ){

         sum*=;

     }

     return sum;

 }

 int n,m;

 ll ans=;

 int main(){

     cin>>n>>m;

     int a[maxn][maxn];

     memset(a,,sizeof(a));

     ll dp[maxn][maxn];

     for( int i=; i<=n; i++ ){

         for( int j=; j<=m; j++ ){

             scanf("%d",&a[i][j]);

         }

     }

     int t=;

     while(t++<n){

         memset(dp,,sizeof(dp));

         for( int i=; i<=m; i++ ){

             for( int j=m; j>=i; j-- ){

                 int len =m-(j-i)-;

             }

         }

 //        for( int i=1; i<=m; i++ ){

 //            for( int j=1; j<=m; j++ ){

 //                cout<<dp[i][j]<<" ";

 //            }

 //            cout<<endl;

 //        }

         ll rev=;

         int i;

         for( i=; i<=m; i++ ){

             ll r=dp[i][i]+a[t][i]*mypow(m);

             if(r>rev) rev=r;

         }

 //        cout<<"rev="<<rev<<endl;

         ans+=rev;

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

矩阵取数问题（dp,高精）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章