首页 > 分享 > 洛谷 P1005 矩阵取数游戏

洛谷 P1005 矩阵取数游戏

花匠小妙招
2024-12-09 09:56

传送门：洛谷 P1005 矩阵取数游戏
算法分析：

每次取数时须从每行各取走一个元素，共 (n) 个。经过 (m) 次后取完矩阵内所有元素；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分(=)被取走的元素值(times 2^i)，其中 (i) 表示第 (i) 次取数（从(1)开始编号）；
游戏结束总得分为 (m) 次取数得分之和。

故只要每一次考虑一行上的状况即可。
设现在在第 (t) 行， (dp[i][j]) 表示最后取 (i) , (j) 能得到的最大分数值，则这一行的答案就为 (dp[1][m])
(dp[i][j]=max{dp[i+1][j]+a[t][i]times2^{m+i-j},dp[i][j+1]+a[t][j]times2^{m+i-j}})
其中 (dp[i][i]=a[i]times 2^m)
附注：本题需用高精度，在本题里使用了重载运算符

时间复杂度：(O(n^3))

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxN=100,maxM=80; struct bign { int len,s[maxN+1]; bign() { memset(s,0,sizeof(s)); len=1; } bign(int num) {*this=num;} bign(const char *num) {*this=num;} bign operator=(const int num) { char s[maxN+1]; sprintf(s,"%d",num); *this=s; return *this; } bign operator=(const char *num) { for(int i=0;num[i]=='0';num++); len=strlen(num); for(int i=0;i<len;i++) s[i]=num[len-i-1]-'0'; return *this; } bign operator+(const bign &b) const { bign c; c.len=0; for(int i=0,g=0;g||i<max(len,b.len);i++) { int x=g; if(i<len) x+=s[i]; if(i<b.len) x+=b.s[i]; c.s[c.len++]=x%10; g=x/10; } return c; } bign operator+=(const bign &b) { *this=*this+b; return *this; } void clear() {while(len>1 && !s[len-1]) len--;} bign operator*(const bign &b) { bign c; c.len=len+b.len; for(int i=0;i<len;i++) for(int j=0;j<b.len;j++) c.s[i+j]+=s[i]*b.s[j]; for(int i=0;i<c.len;i++) { c.s[i+1]+=c.s[i]/10; c.s[i]%=10; } c.clear(); return c; } bign operator*=(const bign &b) { *this=*this*b; return *this; } bool operator<(const bign &b) { if(len!=b.len) return len<b.len; for(int i=len-1;i>=0;i--) if(s[i]!=b.s[i]) return s[i]<b.s[i]; return false; } bool operator>(const bign &b) { if(len!=b.len) return len>b.len; for(int i=len-1;i>=0;i--) if(s[i]!=b.s[i]) return s[i]>b.s[i]; return false; } bool operator==(const bign &b) { return !(*this>b) && !(*this<b); } bool operator!=(const bign &b) { return !(*this==b); } bool operator<=(const bign &b) { return *this<b || *this==b; } bool operator>=(const bign &b) { return *this>b || *this==b; } string str() const { string res=""; for(int i=0;i<len;i++) res=char(s[i]+'0')+res; return res; } }; istream& operator>>(istream &in,bign &x) { string s; in>>s; x=s.c_str(); return in; } ostream& operator<<(ostream &out,const bign &x) { out<<x.str(); return out; } int n,m; bign a[maxM+1][maxM+1]; bign dp[maxM+1][maxM+1]; bign two[maxM+1]; bign ans; inline int read(); void work(int); int main() {n=read(); m=read();ans.clear();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];two[1]=2;for(int i=2;i<=m;i++)two[i]=(bign)2*two[i-1];for(int t=1;t<=n;t++) work(t);cout<<ans; return 0; } void work(int t) {for(int i=0;i<=maxM;i++)for(int j=0;j<=maxM;j++)for(int k=0;k<=maxM;k++)dp[i][j].clear();for(int i=1;i<=m;i++) dp[i][i]=a[t][i]*two[m];for(int len=1;len<m;len++)for(int i=1;i<=m-len;i++){bign x=a[t][i]*two[m-len]+dp[i+1][i+len];bign y=a[t][i+len]*two[m-len]+dp[i][i+len-1];if(x>y) dp[i][i+len]=x;else dp[i][i+len]=y;}ans+=dp[1][m]; } inline int read() { char ch=getchar(); int f=1,num=0; while((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if(ch=='-') {f=-1; ch=getchar();} while(ch>='0' && ch<='9') { num=num*10+ch-'0'; ch=getchar(); } return num*f; }