dp百題進度條[1/100]
一列火車有一個火車頭拖著一長串的車廂，每個車廂有若干個乘客，
一旦火車頭出了故障，所有的車廂就只能停在鐵軌上了，因此鐵路局給每列火車配備了三個迷你火車頭，每個迷你火車頭可以拖動一定數量的車廂，以便火車頭發生故障后能夠拖走部分車廂，
鐵路部門對迷你火車頭作了如下規定：
1．迷你火車頭能夠拖動的最大車廂數是確定的，這個數量對三個迷你火車頭都是相同的，
2．一旦火車頭發生故障，迷你火車頭要拖走盡可能多的旅客，每節車廂的旅客數事先是已知的，并且旅客不得隨意更換車廂，
3．一個迷你火車頭拖走的車廂必須是連續的，所有車廂從1開始編號，
假如有7節車廂，一個迷你火車頭最多可以拖動二節車廂，1到7號車廂中的旅客人數分別為35,40,50,10,30,45和60，
如果三個迷你火車頭拖走的車廂分別是1-2，3-4和6-7，它們帶走的旅客總數將達到240人，其它任何方案都不可能超過該數，所以240就是這個問題的解，
給定車廂數，每節車廂的旅客人數和一個迷你火車頭能拖動的最大車廂數，寫一個程式求出三個迷你火車頭最多能帶走的旅客數，
輸入格式
輸入檔案共有三行，
第一行為一個正整數n，其中n<=50,000，表示車廂總數；
第二行為n個用空格隔開的整數，依次表示n節車廂的旅客人數，每節車廂人數不超過100；
第三行為一個正整數m表示迷你火車頭能夠拖動的最大車廂數，其中m<=n/3，
輸出格式
輸出檔案僅有一行包含一個整數表示三個迷你火車頭最多能帶走的旅客數，
1
測驗樣例1
輸入
7
35 40 50 10 30 45 60
2
輸出
240
我們定義dp[i][j]為第i個火車頭時，拖了前j個車廂的最大值
我們用front陣列來存前綴
狀態轉移方程
dp[i][j] = max_(dp[i][j - 1],dp[i - 1][j - m] + front[j] - front[j - m]);
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 50000 + 5;
int n,t,m;
int dp[5][MAXN],train[MAXN],front[MAXN];
int max_(int x,int y){
if (x > y) return x;
else return y;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for (register int i = 1 ; i <= n ; i++) scanf("%d",&train[i]),front[i] = front[i - 1] + train[i];
scanf("%d",&m);
for (register int i = 1 ; i <= 3 ; i++){
for (int j = m ; j <= n ; j++){
dp[i][j] = dp[i][j - 1];
dp[i][j] = max_(dp[i][j - 1],dp[i - 1][j - m] + front[j] - front[j - m]);
}
}
printf("%d\n",dp[3][n]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/80736.html
標籤：C++
上一篇：vscode搭建C/C++環境