ZOJ@3431题意：有一n层的城堡，每一层有通往下一层的楼梯。对于第i层，通往下层的楼梯在Xi,Yi处；该层有Mi个宝藏，分别给出其坐标和价值；必须在Ti时刻之前（包括）离开，否则楼梯关闭。开始处在第顶层的X,Y处，且每一个单位时刻内可以走一个单位的距离，只能往上下左右四个方向走，通过楼梯不费时间。问能否在规定时间内离开城堡，如果可以的话输出能获得的最大宝藏价值。
解法：动态规划（DP)。
// 2386571 2011-01-15 16:32:37 Accepted 3431 C++ 130 416 redsea
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
using namespace std;
struct Floor{
int m;
int x[8], y[8], value[8];
int t[257],v[257];
}p[105];
int st[105];
int f[2][1205];
inline int abs(int a)
{
return (a>0?a:-a);
}
int main()
{
int T;
int x, y, n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%d%d",&x,&y);
p[0].x[0] = x;
p[0].y[0] = y;
scanf("%d%d",&x,&y);
p[0].x[1] = x;
p[0].y[1] = y;
for(int i = 1; i < n; i++)
{
p[i].x[0] = p[i-1].x[1];
p[i].y[0] = p[i-1].y[1];
scanf("%d%d",&x,&y);
p[i].x[1] = x;
p[i].y[1] = y;
}
for(int i = 0; i < n; i++){
p[i].value[0] = p[i].value[1] = 0;
scanf("%d",&p[i].m);
for(int j = 0; j < p[i].m; j++){
scanf("%d%d%d",&p[i].x[2+j], &p[i].y[2+j], &p[i].value[2+j]);
}
}
for(int i = 0; i < n; i++){
scanf("%d", &st[i]);
}
for(int i = 0; i < n; i++)
for(int j = 0; j < 256; j++){
p[i].t[j] = -1;
p[i].v[j] = -1;
}
for(int i = 0; i < n; i++)
{
int a[6], b[9];
for(int j = 0; j < p[i].m; j++){
a[j] = j+2;
}
p[i].t[3] = abs(p[i].x[0]-p[i].x[1]) + abs(p[i].y[0]-p[i].y[1]);
p[i].v[3] = 0;
b[0] = 0;
do{
for(int j = 0; j < p[i].m; j++)
{
b[j+1] = a[j];
b[j+2] = 1;
int value = 0;
int t = 0;
int s = 0;
s = s | (1<<b[0]);
for(int k = 1; k < j+3; k++){
s = s|(1<<b[k]);
t += abs(p[i].x[b[k]] - p[i].x[b[k-1]]) + abs(p[i].y[b[k]]-p[i].y[b[k-1]]);
value += p[i].value[b[k]];
}
if(p[i].t[s]<0 || p[i].t[s] > t){
p[i].t[s] = t;
p[i].v[s] = value;
}
}
}while(next_permutation(a,a+p[i].m));
}
memset(f,-1,sizeof(f));
f[0][0] = 0;
int a = 1, b = 0;
for(int i = 0; i < n; i++)
{
a = 1-a;
b = 1-b;
for(int j = 0; j < 256; j++){
if(p[i].t[j] < 0 || p[i].v[j] < 0)continue;
for(int k = st[i]; k >= 0; k--){
if(f[a][k] >= 0 && k+p[i].t[j] <= st[i] && f[b][k+p[i].t[j]] < f[a][k]+p[i].v[j])
f[b][k+p[i].t[j]] = f[a][k]+p[i].v[j];
}
}
if(i==0)
f[a][0] = -1;
else{
for(int j = 0; j <= st[i-1]; j++)
f[a][j] = -1;
}
}
int ans = -1;
for(int i = 0; i <= st[n-1]; i++)
{
if(f[b][i]>ans)ans = f[b][i];
}
if(ans>=0)printf("%d\n",ans);
else printf("I'm doomed, though I fought bravely\n");
}
return 0;
}