圖解
@光巨
Description
“拔出石中劍，你便是王”，
“拔劍之前,你最好先想一想，因為一旦拔起劍，你將不再是人類,你會被所有人類憎惡，你將最終迎來悲劇的死亡，”魔術師梅林如是說，
然而名為Arturia Pendragone的少女還是拔起了劍，成為了英格蘭之王，
一天，王發現她拔出的石中劍上有N個凹槽，經過多年征戰，她一共收集了M塊寶石，并且N≥M，將每塊寶石放到每一個凹槽中都會使石中劍具有一定的美麗值（可能為負數），
若1≤i<j≤M，則編號為i的寶石所在的凹槽的編號一定要小于編號為j的寶石所在的凹槽的編號，
由于王也是女孩子，所以她希望這個美麗值最大，
當然，每個凹槽只能放入一 塊寶石，每塊寶石也只能放入一個凹槽，
每塊寶石都必須被使用到，
Input
第一行，兩個整數N,M；
接下來M行，每行N個整數，表示這一塊寶石放入這一個凹槽的美麗值，
Output
一行，表示美麗值的最大可能值，
Input Copy
3 2
-10 10 10
0 30 10
Output
20
Hint
【資料范圍】
對于10%的資料，M=1
另外20%的資料，1≤M≤5 M≤N≤20
對于100%的資料，1≤M≤N≤1500
每個寶石的美麗值保證大于?105，小于105
題目大意：
m行n列的矩陣，從一行開始每一行可以選擇一個位置的權值
但是如果第一行選擇的第j列的位置
那么再往下選的時候只能選大于j 列的列
題目思路：
dp[i][j] 代表第i個寶石 放在第j個坑的最大值
樸素方程 dp[i][j] = dp[i-1][k] + val[i][j]; k<j
此時發現 需要三層回圈
但是時間復雜度并不允許
可以用前綴的最大值優化掉 dp[i-1][k] 這一項
新的方程為
dp[i][j] = max(dp[i][j],pre[j-1]+val[i][j]);
pre[j-1] 是上一行中的寶石放在了j-1列之前的列的最大值
當然pre陣列也可以開二維（類似背包）
Code：
int n,m,val[2212][2221],s[2121][2221],num[2121],dp[2121][2121],pre[2211];
int main() {
n=read(),m=read();
rep(i,0,n) rep(j,0,m) dp[i][j] = -inf;
rep(i,1,m) rep(j,1,n) val[i][j] = read();
for(int i=1 ; i<=m ; i++) {
for(int j=i ; j<=n ; j++) dp[i][j] = max(dp[i][j],pre[j-1]+val[i][j]);
for(int j=i ; j<=n ; j++) {
num[j] = dp[i][j];
if(j==i) pre[j] = num[j];
else pre[j] = max(pre[j-1],num[j]);
}
}
int ans = -inf;
for(int i=m ; i<=n ; i++) ans = max(ans,dp[m][i]);
out(ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253557.html
標籤：其他
上一篇：GDKOI2021普及DAY1