【b703】矩陣取數游戲

2019-11-14 09:00:29

字體：大中小

來源：轉載

供稿：網友

Time Limit: 1 second Memory Limit: 50 MB

【問題描述】

帥帥經常跟同學玩一個矩陣取數游戲：對于一個給定的n*m的矩陣，矩陣中的每個元素aij均為非負整數。游戲規則如下：1. 每次取數時須從每行各取走一個元素，共n個。m次后取完矩陣所有的元素；2. 每次取走的各個元素只能是該元素所在行的行首或行尾；3. 每次取數都有一個得分值，為每行取數的得分之和；每行取數的得分 = 被取走的元素值*2i，其中i表示第i次取數（從1開始編號）；4. 游戲結束總得分為m次取數得分之和。帥帥想請你幫忙寫一個程序，對于任意矩陣，可以求出取數后的最大得分。

【輸入】

包括n+1行；第一行為兩個用空格隔開的整數n和m。第2~n+1行為n*m矩陣，其中每行有m個用單個空格隔開

【輸出】

僅包含1行，為一個整數，即輸入矩陣取數后的最大的分。

【輸入樣例1】

2 31 2 33 4 2

【輸出樣例1】

【輸入輸出樣例1解釋】

第1次：第一行取行首元素，第二行取行尾元素，本次的氛圍1*21+2*21=6第2次：兩行均取行首元素，本次得分為2*22+3*22=20第3次：得分為3*23+4*23=56。總得分為6+20+56=82

【輸入樣例2】

1 44 5 0 5

【輸出樣例2】

122

【輸入樣例3】

2 1096 56 54 46 86 12 23 88 80 4316 95 18 29 30 53 88 83 64 67

【輸出樣例3】

316994

【限制】

60%的數據滿足：1<=n, m<=30，答案不超過1016100%的數據滿足：1<=n, m<=80，0<=aij<=1000

【題目鏈接】:http://noi.qz5z.com/viewtask.asp?id=b703

【題意】中文題

【題解】這道題可以分成n個步驟; 即每一行與每一行之間是獨立的; 所以我們可以一行一行地進行處理; 設 f[i][j]表示取當前行區間[i..j]內的數能夠獲得的最大值; 則 f[i][j] = 2*max(a[i]+f[i+1][j],f[i][j-1]+a[j]); 這里的2對外層的區間乘的次數比較少,對內層的區間里的數乘得比較多; 且從內到外是遞增1的; 正符合題目的要求; 寫一個記憶化搜索就好了; 因為數據比較大; 要寫一個高精度; 。。。挺麻煩的。 (一開始那個a數組沒有init調了很久。。做高精度加法的時候要注意啊,不然之前的數據會保留下來的。。) 【完整代碼】

#include <cstdio>#include <algorithm>#include <cmath>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%I64d",&x)typedef pair<int,int> pii;typedef pair<LL,LL> pll;const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int MAXM = 110;struct bignum{ int a[110],len; void init() { rep1(i,1,100) a[i] = 0; }};int n,m;bignum f[MAXM][MAXM],emp,a[MAXM],ans;bignum plu(bignum a,bignum b){ bignum c; rep1(i,1,100) c.a[i] = 0; c.len = max(a.len,b.len); int x = 0; rep1(i,1,c.len) { c.a[i] = c.a[i] + a.a[i]+b.a[i] + x; x = c.a[i]/10; c.a[i] %= 10; } while (x>0) { c.a[++c.len] = x; x = c.a[c.len]/10; c.a[c.len]%=10; } return c;}bignum ma(bignum a,bignum b){ int len1 = a.len,len2 = b.len; if (len1>len2) return a; else if (len1<len2) return b; rep2(i,len1,1) if (a.a[i]!=b.a[i]) { if (a.a[i]>b.a[i]) return a; else return b; } return a;}bignum dfs(int l,int r){ if (l>r) return emp; if (f[l][r].a[1]!=-1) return f[l][r]; if (l==r) return plu(a[l],a[l]); //f[l][r] = 2*max(a[l]+dfs(l+1,r),dfs(l,r-1)+a[r]); bignum temp1 = plu(a[l],dfs(l+1,r)); bignum temp2 = plu(dfs(l,r-1),a[r]); bignum temp3 = ma(temp1,temp2); return f[l][r] = plu(temp3,temp3);}int main(){ //freopen("F://rush.txt","r",stdin); ans.len = 1;ans.a[1] =0;ans.init(); emp.a[1] = 0,emp.len = 1; emp.init(); rei(n);rei(m); rep1(i,1,n) { rep1(ii,1,m) rep1(jj,1,m) { f[ii][jj].init(); f[ii][jj].len = 1; f[ii][jj].a[1] = -1; } rep1(j,1,m) { int temp,len=0; rei(temp); a[j].init(); while (temp>0) { a[j].a[++len] = temp%10; temp/=10; } if (len==0) { a[j].a[1] = 0; a[j].len = 1; } else a[j].len = len; } ans=plu(ans,dfs(1,m)); } rep2(i,ans.len,1)