本文共 1341 字，大约阅读时间需要 4 分钟。
题意：N个歹徒去一个餐馆，餐馆门有k个打开程度（每个打开程度为门的一个状态），每个歹徒拥有各自的肥胖度和繁荣度（prosperity），歹徒在i 时刻到达餐馆，若此时刻门的打开程度与歹徒的肥胖度完全相同，则歹徒就进入餐馆，同时餐馆获得这个歹徒相应的繁荣度，若歹徒到来时门的打开程度与歹徒的肥胖程度不同，则歹徒离开且不再回来。门的打开程度在每个单位时间里可以加1、减1或不变。
要求：通过控制门的打开程度，使餐馆最后获得最大的繁荣度，最初门的打开程度为0。
算法：dp
先按到达餐馆的时刻对歹徒进行升序排序
设dp[i]为前i个歹徒到达餐馆时餐馆获得的最大繁荣度
dp[i] = max{dp[j]+pi} 1 <= j < i
#include #include #include using namespace std;int N,K,T;int dp[101]; // dp[t][k]=j: t时刻门的状态为k时所获得的最大繁荣度是jstruct GANGSTER{ int t; int p; int s;};GANGSTER gangsters[101];bool cmp(const GANGSTER &a, const GANGSTER &b){ return a.t < b.t;}int main(){ while (cin >> N >> K >> T) { memset(dp,0,sizeof(dp)); for (int i=1; i<=N; i++) { cin >> gangsters[i].t; } for (int i=1; i<=N; i++) { cin >> gangsters[i].p; } for (int i=1; i<=N; i++) { cin >> gangsters[i].s; } sort(gangsters,gangsters+N+1,cmp); // 此处是gangsters+N+1，不是gangsters+N，WA数次！！！ int ans = 0; // 依次处理前i个gangster for (int i=1; i<=N; i++) { if (gangsters[i].t > T) { break; } if (gangsters[i].s > gangsters[i].t) { continue; } for (int j=0; j = abs(gangsters[i].s-gangsters[j].s)) { // dp[i]=max{dp[j]+pi} if (dp[i] < dp[j] + gangsters[i].p) { dp[i] = dp[j] + gangsters[i].p; } } if (dp[i] > ans) { ans = dp[i]; } } } cout << ans << endl; }}
转载地址：http://trlbb.baihongyu.com/