TOJ 3232 TOJギフト両替
1681 ワード
3232:TOJギフト両替
時間制限(通常/Java):1000 MS/3000 MSメモリ制限:65536 KByte総提出:136テスト合格:91
説明
最近crq先生は各学生のACMに対する興味を高めるために、TOJにポイント制度と贈り物の両替機能を追加しました.TOJのポイントは容易ではありません.学生たちは同じポイントで最大の価値の贈り物を交換したいと思っていますが、ある学生はMのポイントでいくつかの贈り物を交換しました.彼はMのポイントで最大いくらの価値の贈り物を交換することができますか?(ポイントMは必ず使い切る)
入力
入力データはまず正の整数Cを含み、C群の試験用例を示し、各群の試験用例の第1行は2つの整数MとN(1<=M<=1000、1<=N<=100)であり、それぞれ交換した総積分と贈り物の種類を表し、次いでN行のデータであり、各行は3つの数p、hとc(1<=p<=100、0<=h<=200、1<=c<=1000)を含み、それぞれ各贈り物の価格、対応する種類の贈り物の残りの数と各種類の贈り物の消費のポイント.
しゅつりょく
各テストデータのセットについて、Mが使用できる場合は「The maximum value is X.」を出力し、そうでない場合は「This is impossible.」を出力する.同じ種類のものを何度も交換できると仮定することができます.各インスタンスの出力は1行を占めます.
サンプル入力
サンプル出力
テーマソース
TOJ
時間制限(通常/Java):1000 MS/3000 MSメモリ制限:65536 KByte総提出:136テスト合格:91
説明
最近crq先生は各学生のACMに対する興味を高めるために、TOJにポイント制度と贈り物の両替機能を追加しました.TOJのポイントは容易ではありません.学生たちは同じポイントで最大の価値の贈り物を交換したいと思っていますが、ある学生はMのポイントでいくつかの贈り物を交換しました.彼はMのポイントで最大いくらの価値の贈り物を交換することができますか?(ポイントMは必ず使い切る)
入力
入力データはまず正の整数Cを含み、C群の試験用例を示し、各群の試験用例の第1行は2つの整数MとN(1<=M<=1000、1<=N<=100)であり、それぞれ交換した総積分と贈り物の種類を表し、次いでN行のデータであり、各行は3つの数p、hとc(1<=p<=100、0<=h<=200、1<=c<=1000)を含み、それぞれ各贈り物の価格、対応する種類の贈り物の残りの数と各種類の贈り物の消費のポイント.
しゅつりょく
各テストデータのセットについて、Mが使用できる場合は「The maximum value is X.」を出力し、そうでない場合は「This is impossible.」を出力する.同じ種類のものを何度も交換できると仮定することができます.各インスタンスの出力は1行を占めます.
サンプル入力
3
700 3
10 2 100
65 5 500
24 10 200
273 4
57 190 53
51 66 383
92 65 91
61 126 364
273 2
57 190 53
61 126 364
サンプル出力
The maximum value is 89.
The maximum value is 276.
This is impossible.
テーマソース
TOJ
#include
#include
int main()
{
int n,i,j,l,m,t,q[1005],p,h,c;
scanf("%d",&t);
while(t--)
{
memset(q,0,sizeof(q));
scanf("%d %d",&m,&n);
while(n--)
{
scanf("%d %d %d",&p,&h,&c);
for(i=0;i=c;j--)
{
if(q[c]q[j])
{
q[j]=q[j-c]+p;
}
}
}
}
if(q[m])
printf("The maximum value is %d.
",q[m]);
else
printf("This is impossible.
");
}
}