ZOJ@3431題意：有一n層的城堡，每一層有通往下一層的樓梯。對(duì)于第i層，通往下層的樓梯在Xi,Yi處；該層有Mi個(gè)寶藏，分別給出其坐標(biāo)和價(jià)值；必須在Ti時(shí)刻之前（包括）離開，否則樓梯關(guān)閉。開始處在第頂層的X,Y處，且每一個(gè)單位時(shí)刻內(nèi)可以走一個(gè)單位的距離，只能往上下左右四個(gè)方向走，通過樓梯不費(fèi)時(shí)間。問能否在規(guī)定時(shí)間內(nèi)離開城堡，如果可以的話輸出能獲得的最大寶藏價(jià)值。
解法：動(dòng)態(tài)規(guī)劃（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;
}