[UVA][dp] 672 - Gangsters
Gangsters
| Gangsters |
N gangsters are going to a restaurant. The i-th gangster comes at thetime Ti and has the prosperity Pi. The door of the restaurant hasK+1 states of openness expressed by the integers in the range [0, K]. Thestate of openness can change by one in one unit of time; i.e. it either opensby one, closes by one or remains the same. At the initial moment of time thedoor is closed (state 0). The i-th gangster enters the restaurant only if thedoor is opened specially for him, i.e. when the state of openness coincideswith his stoutness Si. If at the moment of time when the gangstercomes to the restaurant the state of openness is not equal to his stoutness,then the gangster goes away and never returns.
The restaurant works in the interval of time [0, T].
The goal is to gather the gangsters with the maximal total prosperity in the restaurant by opening and closing the door appropriately.
Input
The first line of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets.The first line of each dataset contains the values N, K, and T,separated by spaces. (
)
The second line of the dataset contains the moments of time whengangsters come to the restaurant 
,separated byspaces. (
for 
)
The third line of the dataset contains the values of the prosperity ofgangsters 
,separated by spaces. (
for )
The forth line of the dataset contains the values of the stoutness ofgangsters 
,separated by spaces. (
for)
All values in the input file are integers.
Output
For each dataset, print the single integer - the maximal sum of prosperity of gangsters in the restaurant. In case when nogangster can enter the restaurant the output should be 0.Print a blank line between datasets.Sample Input
14 10 2010 16 8 1610 11 15 110 7 1 8
Sample Output
26
Miguel Revilla
2000-05-22
題目描述：
一家餐館現在陸陸續續有 N 位流氓來訪，這家店的門很特殊，每個時刻可以變大+1不變+0變小-1，
第 0 時刻大小為 0，而每個流氓來時，如果門大小剛好等於他所要求的，他便會進來消費。
反之則否，求最大消費總額。
題目解法：
對時間狀態作 DP，dp[i][j] : 在時間 i 門大小 j 的最大消費總額。
// 一開始想對時間排序，把時間 i 替換成第 i 個人，由於時間可能會重疊，處理較為複雜。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Gangster {
int t, p, s;
};
int dp[30005][105], w[30005][105];
int main() {
int testcase;
int N, K, T;
int i, j, k;
Gangster D[105];
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &N, &K, &T);
for(i = 1; i <= N; i++) scanf("%d", &D[i].t);
for(i = 1; i <= N; i++) scanf("%d", &D[i].p);
for(i = 1; i <= N; i++) scanf("%d", &D[i].s);
memset(w, 0, sizeof(w));
memset(dp, 0, sizeof(dp));
for(i = 1; i <= N; i++)
w[D[i].t][D[i].s] += D[i].p;
int ret = 0;
for(i = 0; i < T; i++) {
for(j = min(i, K); j >= 0; j--) {
if(j)
dp[i+1][j-1] = max(dp[i+1][j-1], dp[i][j] + w[i+1][j-1]);
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + w[i+1][j]);
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + w[i+1][j+1]);
}
}
for(i = 0; i <= K; i++)
ret = max(ret, dp[T][i]);
printf("%d\n", ret);
if(testcase)
puts("");
}
return 0;
}