轉跳P1005

題目描述
帥帥經常跟同學玩一個矩陣取數游戲：對于一個給定的 n \times mn×m 的矩陣，矩陣中的每個元素 a_{i,j}a
i,j
?
均為非負整數。游戲規則如下：

每次取數時須從每行各取走一個元素，共 nn 個。經過 mm 次后取完矩陣內所有元素；
每次取走的各個元素只能是該元素所在行的行首或行尾；
每次取數都有一個得分值，為每行取數的得分之和，每行取數的得分 = 被取走的元素值 \times 2^i×2
i
，其中 ii 表示第 ii 次取數（從 11 開始編號）；
游戲結束總得分為 mm 次取數得分之和。
帥帥想請你幫忙寫一個程序，對于任意矩陣，可以求出取數后的最大得分。

輸入格式
輸入文件包括 n+1n+1 行：

第一行為兩個用空格隔開的整數 nn 和 mm。

第 2\backsim n+12∽n+1 行為 n \times mn×m 矩陣，其中每行有 mm 個用單個空格隔開的非負整數。

輸出格式
輸出文件僅包含11行，為一個整數，即輸入矩陣取數后的最大得分。

輸入輸出樣例
輸入 #1復制
2 3
1 2 3
3 4 2
輸出 #1復制
82
說明/提示
NOIP 2007 提高第三題。

數據范圍：

60%60% 的數據滿足：1\le n,m\le 301≤n,m≤30，答案不超過 10^{16}10
16
。

100%100% 的數據滿足：1\le n,m\le 801≤n,m≤80，0\le a_{i,j}\le10000≤a
i,j
?
≤1000。

思路：是一個簡單dp，沒啥好說，算出沒有行的數值加起來就好了。

重點的__int128 的模板；

#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se secondusing namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int > pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=1e9+7; const ll N =1e6; const double eps = 1e-4; const double pi=acos(-1); ll gcd(int a,int b){return !b?a:gcd(b,a%b);} __int128 ans=0; __int128 dp[100][100]; int a[100][100]; int n,m; __int128 p[100]; __int128 dp1(int x) {FILL(dp,0);for(int i=1;i<=m;i++){for(int j=m;j>=i;j--){dp[i][j]=max(dp[i-1][j]+a[x][i-1]*p[m-j+i-1],dp[i][j+1]+a[x][j+1]*p[m-j+i-1]);}}__int128 ans=0;for(int i=1;i<=m;i++) ans=max(ans,dp[i][i]+a[x][i]*p[m]);return ans; } void print(__int128 x) {if(x<0) return;if(x>9) print(x/10);putchar(x%10+'0'); } int main(){ioscin>>n>>m;p[1]=2;for(int i=2;i<=80;i++) p[i]=p[i-1]*2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}ans+=dp1(i);}print(ans); }

__int128的輸入輸出模板：

inline __int128 read() {__int128 x = 0, f = 1;char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch - '0');ch = getchar();}return x * f; } void print(__int128 x) {if (x < 0){putchar('-');x = -x;}if (x > 9)print(x / 10);putchar(x % 10 + '0'); }

總結

以上是生活随笔為你收集整理的P1005 矩阵取数游戏（__int128模板/简单dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。