[TIOJ] 1268. 得分高手 (Master)

題目連結:http://tioj.infor.org/problems/1268
想了兩下後發現可以DP,狀態也很簡單就是$dp[i][j]$代表結尾在$(i,j)$時的最大值,轉移就只要$dp[i][j]=max(0, dp[i-1][j], dp[i][j-1])+mtx[i][j]$其中mtx代表原始的數字。
#include <bits/stdc++.h>
using namespace std;
const int N = 3000 + 5;

int mtx[N][N], dp[N][N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m, ans=0; cin>>n>>m;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
		cin>>mtx[i][j];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(i-1 >= 0) dp[i][j] = max(dp[i-1][j], dp[i][j]);
			if(j-1 >= 0) dp[i][j] = max(dp[i][j-1], dp[i][j]);
			dp[i][j]+=mtx[i][j];
			ans = max(ans, dp[i][j]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology