题意：有N个教父要进一家餐馆，每个人有一个自己的成功度Pi，有自己体型的大小Si，到餐馆的时刻分别是Ti。餐馆的门可打开[0, K]的空间（初始状态是0），单位时间能改变1的空间，营业时间是[0, T]。当门的状态与体型大小相等时教父才会进去，否则离开不再回来。问如何调整门的状态，使得进去的教父的成功度的和最大。(1 <= N <= 100 ,1 <= K <= 100 ,0 <= T <= 30000, 0 <= Ti <= T, 0 <= Pi <= 300, 1 <= Si <= K)
题目链接：http://poj.org/problem?id=1036
——>>状态：设d[i][j]表示时刻i门的开闭状态为j时的最大成功度的和
状态转移方程：d[i][[j] = max(d[i-1][j], d[i-1][j-1], d[i-1][j+1]) + 能新增的成功度
优化空间：d[i&1][j] = max(d[1-(i&1)][j], d[1-(i&1)][j-1], d[1-(i&1)][j+1]) + 能新增的成功度
要求时刻i门开闭状态为j时能新增的成功度，可以累计。。
时间复杂度：O(m*n^2)
写完之后，提交TLE了。。
再改，当时刻有教父出现才累计新增的成功度。。AC
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;#define jj (i&1)const int maxn = 100 + 10;int t[maxn], p[maxn], s[maxn];
int d[2][maxn];
bool vis[30000+10];int main()
{int N, K, T;while(scanf("%d%d%d", &N, &K, &T) == 3) {memset(vis, 0, sizeof(vis));for(int i = 1; i <= N; i++) {scanf("%d", t+i);vis[t[i]] = true;}for(int i = 1; i <= N; i++) scanf("%d", p+i);for(int i = 1; i <= N; i++) scanf("%d", s+i);memset(d, 0, sizeof(d));for(int i = 0; i <= T; i++) {for(int j = 0; j <= i && j <= K; j++) {int w = 0;if(vis[i]) {for(int k = 1; k <= N; k++)if(t[k] == i && s[k] == j)w += p[k];}d[jj][j] = d[1-jj][j];if(j-1 >= 0) d[jj][j] = max(d[jj][j], d[1-jj][j-1]);if(j+1 <= K) d[jj][j] = max(d[jj][j], d[1-jj][j+1]);d[jj][j] += w;}}int Max = -1;for(int i = 0; i <= K; i++)if(d[T&1][i] > Max)Max = d[T&1][i];printf("%d\n", Max);}return 0;
}