話說(shuō)這道題是一道01背包了，糾結(jié)的就是那個(gè)糟爛的輸入，因?yàn)檩斎耄壹m結(jié)了得有一個(gè)小時(shí)，但是最后還是成功了…… 還好樣例吧所有的陷阱都給了，否則不知道要WA多少次，可恨的是我CE了一次，TMD復(fù)制粘貼的時(shí)候搞錯(cuò)了，這要是正式比賽，那個(gè)罰時(shí)啊……   view code
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int c[500], i, v, num[500], j, n, tot, ju[3];
double cc, vv, sum, x, dp[4000000];
char c1, c2, c3;
bool f;
int max(int a, int b)
{
if (a > b) return a;
else return b;
}
int main()
{
while (cin >> vv >> n && n != 0)
{
v = (int)(vv * 100);
tot = 0;
memset(c, 0, sizeof(c));
memset(dp, 0, sizeof(dp));
for (i = 1; i <= n; i++)
{
cin >> num[i];
f = 1; sum = 0;
memset(ju, 0, sizeof(ju));
for (j = 1; j <= num[i]; j++)
{
scanf(" %c:%lf", &c1, &cc);
if (c1 == 'A') ju[0] += cc;
else if (c1 == 'B') ju[1] += cc;
else if (c1 == 'C') ju[2] += cc;
else f = 0;
sum += cc;
}
if (sum <= 1000 && ju[0] <= 600 && ju[1] <= 600 && ju[2] <= 600 && f == 1)
{
tot++;
c[tot] = sum * 100;
}
}
for (i = 1; i <= tot; i++)
for (j = v; j >= c[i]; j--)
dp[j] = max(dp[j], dp[j - c[i]] + c[i]);
x = (double)(dp[v] / 100);
printf("%.2lf\n", x);
}
return 0;
}
|