題目傳送門
前言
今天依舊是不寫高精的一天呢！（是的，這位作者又只拿了開 \(LL\) 的 \(\color{yellow}{60}\) 分）
思路描述
看到資料 \(n,m \le 80(30)\) 就知道陣列可以任性開，心理有個底后，再來看題目，
狀態描述
首先肯定要來一個 \(dp_{i,j}\) 來表示第 \(i\) 次時取第 \(j\) 行的數，
對于每一次放置，我們要考慮到的是之前每一次都取到什么,也就是現在的頭和尾分別是哪兩個數，
想明白這一點，就可以描述狀態了，
\(dp_{i,j,k,t}\) 表示第 \(i\) 次時取第 \(j\) 行的數，對于第 \(j\) 行，它的行首被取了 \(k\) 個數，他的行尾被取了 \(t\) 個數，
由于 $t = i - k $ ，當 \(i，k\) 確定時，\(t\) 也一定唯一，因此可以省略，
狀態轉移方程
描述出狀態了，狀態轉移方程還會遠嗎？
顯然有
\(dp_{i,j,k} = \max(dp_{i-1,j,k-1}+val（i,j,k）,dp_{i-1,j,k}+val(i,j,m-(i-k)+1))\)，
\(val(x,y,z)\) 表示第 \(x\) 次時取位于第 \(y\) 行第 \(z\) 列的數所能獲得的得分，
\(\max\) 中的兩者分別對應了第 \(i\) 次時，在第 \(j\) 行取隊首 \(or\) 隊尾的情況，
code
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll a[85][85],dp[85][85][85];
int bas[31];
int main(){
scanf("%d%d",&n,&m);
bas[0]=1;
for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dp[i][j][i]=dp[i-1][j][i-1]+a[j][i]*bas[i],dp[i][j][0]=dp[i-1][j][0]+a[j][m-i+1]*bas[i];//這兩種情況比較特殊，所以單獨列，
for(int k=1;k<i;k++){
dp[i][j][k]=max(dp[i-1][j][k-1]+a[j][k]*bas[i],dp[i-1][j][k]+a[j][m-(i-k)+1]*bas[i]);
}
}
}
ll ans=0;
for(int i=1;i<=n;i++){
ll max_num=0;
for(int j=0;j<=m;j++)
max_num=max(max_num,dp[m][i][j]);
ans+=max_num;
}
cout<<ans<<endl;
return 0;
}
ps：經過作者后續習慣性翻翻題解（發現原來區間DP也可以做），以及打輸出時的共同啟發，發現實際上我們只需要分別列舉對于每一行是的最優解，加起來就可以了，因此狀態中表示行的那一維可以省略，然后就有了以下代碼，
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,m;
ll a[85][85],dp[85][85];
int bas[31];
int main(){
scanf("%d%d",&n,&m);
bas[0]=1;
for(int i=1;i<=30;i++) bas[i]=bas[i-1]*2;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
ll ans=0,max_num;
for(int j=1;j<=n;j++){
for(int i=1;i<=m;i++){
dp[i][i]=dp[i-1][i-1]+a[j][i]*bas[i],dp[i][0]=dp[i-1][0]+a[j][m-i+1]*bas[i];
for(int k=1;k<i;k++){
dp[i][k]=max(dp[i-1][k-1]+a[j][k]*bas[i],dp[i-1][k]+a[j][m-(i-k)+1]*bas[i]);
}
}
max_num=0;
for(int i=0;i<=m;i++) max_num=max(max_num,dp[m][i]);
ans+=max_num;
}
cout<<ans<<endl;
return 0;
}
事實上沒太大區別，畢竟它的資料范圍可以讓我任性開（首尾呼應.jpg(確信)），
summary
對于省略維數有了更深刻的理解，
-
可以用其他維度表示的可以省略，
-
可以通過分開解決時不需要整體來定義，
\(dp\)百道第六題，（照這個進度可能得一年后在看看有沒有百道的希望了QWQ）
加油，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541793.html
標籤：C++
上一篇：C++學習筆記 （2）
下一篇：函式執行順序