【問題描述】
幽暗城皇家鍊金師赫布瑞姆剛剛發明瞭一種用來折磨戰俘的新型藥 劑，這種藥劑被稱爲靈魂分流藥劑。靈魂分流藥劑的妙處在於能夠給戰俘帶來巨大的痛苦，但是卻不會讓戰俘死去。這種藥劑中包含了一些治療的成分，所以即使戰 俘想自盡，也會被救活。用這種求生不得，求死不能的感覺，來對付反對希爾瓦娜斯女王的狂徒們，實在是太美妙了。當然，靈魂分流藥劑要限定在一個用量範圍之 內，過少會達不到效果，而過多會直接殺了戰俘。
最近，我們抓獲了一個來自暴風城的探子，他掌握了我們的許多重要情報。希爾瓦娜斯女王命令你用最痛苦的手段折磨他。你從你的導師，靈魂分流藥劑的發明者——皇家鍊金師赫布瑞姆那裏獲得了N瓶藥劑。每瓶按照藥性的不同裝在M個箱子中。每瓶藥劑都有一個規格：對服用者造成的肉體傷害w，對服用者造成的意志折磨v，所屬的箱子t，和對服用者造成的痛苦值p。
據我們測試，那個暴風城探子的生命值爲A，意志力爲B。你要從每個箱子中最多拿取1瓶藥劑餵給他。注意，餵給他的藥劑造成的總肉體傷害不能超過他的生命值A，否則他會死去，總意志折磨不能超過他的意志力B，否則他會精神崩潰，我們沒有必要給一個精神崩潰的傻瓜製造那麼多痛苦。在不讓他死去或者精神崩潰的前提下，你要儘可能多的給他製造痛苦，你能解決這個問題嗎？
輸入格式
第1行：四個整數N,M,A,B，M個箱子的編號爲1..M。
第2行至第N+1行：第i+1行四個整數w,v,t,p表示第i瓶藥劑的肉體傷害，意志折磨，所屬箱子的編號，和造成的痛苦值。
輸出格式
第1行：一個整數，表示能夠造成的最大的痛苦值。
樣例輸入
5 3 20 20
5 10 1 200
10 5 1 100
8 11 2 56
10 10 2 50
5 5 3 100
樣例輸出
300
數據規模
對於30%的數據
N<=30
M<=5
對於100%的數據
N<=100
M<=10
A,B<=100
【分析】
經典的動態規劃，0/1背包問題。
以每個箱子為階段劃分狀態，而每個箱子又是一個最優子問題。
狀態設定
Box[i].W[j]：第i個箱子中第j件物品的肉體傷害
Box[i].V[j]：第i個箱子中第j件物品的意志折磨
Box[i].P[j]：第i個箱子中第j件物品的傷害值
Box[i].num：第i個箱子中 藥劑的總數
F[k][i][j] ：對於前k個箱子，當探子生命值為i，意志力為j時的最大傷害值
邊界條件：
F[0][i][j]=0
狀態轉移方程：
F[k][i][j]= Max{ Max{F[k-1][i-Box[k].W[m]][j-Box[k].V[m]]+Box[k].P[m]} , F[k-1][i][j] } (1<=m<=Box[k].num)
目標狀態：
F[M][A][B]
【我的代碼】
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int F[11][101][101];
class BOX
{
public:
int num;
int W[101];
int V[101];
int P[101];
BOX()
{
num=0;
}
}Box[11];
int N,M;
int A,B;
void init()
{
scanf("%d %d %d %d\n",&N,&M,&A,&B);
int w,v,t,p;
for (int i=1;i<=N;i++)
{
scanf("%d %d %d %d\n",&w,&v,&t,&p);
Box[t].num++;
Box[t].W[Box[t].num]=w;
Box[t].V[Box[t].num]=v;
Box[t].P[Box[t].num]=p;
}
return;
}
void dynamic()
{
int tmp;
for (int i=1;i<=A;i++)
for (int j=1;j<=B;j++)
F[0][i][j]=0;
for (int k=1;k<=M;k++)
{
for(int i=1;i<=A;i++)
{
for (int j=1;j<=B;j++)
{
int Max=0;
for (int m=1;m<=Box[k].num;m++)
{
if(i-Box[k].W[m]>=0 && j-Box[k].V[m]>=0)
{
tmp=F[k-1][i-Box[k].W[m]][j-Box[k].V[m]]+Box[k].P[m];
if(tmp>Max)
Max=tmp;
}
}
if (F[k-1][i][j]>Max)
Max=F[k-1][i][j];
F[k][i][j]=Max;
}
}
}
printf("%d\n",F[M][A][B]);
}
int main()
{
freopen("soultap.in","r",stdin);
freopen("soultap.out","w",stdout);
init();
dynamic();
return 0;
}
【評測結果】
正在连接评测机...
已连接到评测机
| GRID |
1 |
| 名称 |
Flitty |
| 系统版本 |
1.00 |
| 备注 |
COGS 1号评测机 Flitty |
正在编译...
编译成功
| 测试点 |
结果 |
得分 |
运行时间 |
内存使用 |
退出代码 |
| 1 |
正确 |
10 |
0.000 s |
724 KB |
0 |
| 2 |
正确 |
10 |
0.006 s |
724 KB |
0 |
| 3 |
正确 |
10 |
0.001 s |
724 KB |
0 |
| 4 |
正确 |
10 |
0.001 s |
724 KB |
0 |
| 5 |
正确 |
10 |
0.005 s |
724 KB |
0 |
| 6 |
正确 |
10 |
0.006 s |
724 KB |
0 |
| 7 |
正确 |
10 |
0.006 s |
724 KB |
0 |
| 8 |
正确 |
10 |
0.006 s |
724 KB |
0 |
| 9 |
正确 |
10 |
0.006 s |
724 KB |
0 |
| 10 |
正确 |
10 |
0.006 s |
724 KB |
0 |
运行完成
运行时间 0.042 s
平均内存使用 724 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
