测评机： Xeost[5]
得分： 80分
提交日期： 2011-9-27 19:28:00
有效耗时： 454毫秒
测试结果1: 通过本测试点|有效耗时125ms
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 通过本测试点|有效耗时47ms
测试结果5:
测试结果6:
测试结果7: 通过本测试点|有效耗时47ms
测试结果8: 通过本测试点|有效耗时47ms
测试结果9: 通过本测试点|有效耗时47ms
测试结果10: 通过本测试点|有效耗时47ms
提交代码：
view sourceprint?
001.
#include <cstdio>
002.
#include <iostream>
003.
#include <cstring>
004.
#include <vector>
005.
006.
using namespace std;
007.
008.
int value[100][10] = {{0}};
009.
int wast[100][10] = {{0}};
010.
int n,m;
011.
long ans;
012.
int f[4000][100] = {{0}};
013.
int map[200];
014.
int flag = 0;
015.
016.
void init()
017.
{
018.
//freopen("ex.in","r",stdin);
019.
cin>>n>>m;
020.
n = n/10;
021.
for (int i=1; i<=m; i++)
022.
{
023.
int t_1,t_2,t_3;
024.
cin>>t_1>>t_2>>t_3;
025.
t_1 = t_1/10;
026.
if (t_3 == 0)
027.
{
028.
flag++;
029.
value[flag][0]++;
030.
value[flag][1] = t_1*t_2;
031.
map[i] = flag;
032.
wast[flag][0]++;
033.
wast[flag][1]=t_1;
034.
}
035.
else
036.
{
037.
value[map[t_3]][0]++;
038.
value[map[t_3]][value[map[t_3]][0]] = t_1*t_2;
039.
wast[map[t_3]][0]++;
040.
wast[map[t_3]][wast[map[t_3]][0]]=t_1;
041.
042.
}
043.
}
044.
for (int i=1; i<=m; i++)
045.
{
046.
if (value[i][0] == 2)
047.
{
048.
value[i][0];
049.
wast[i][0];
050.
value[i][2] = value[i][1]+value[i][2];
051.
wast[i][2] = wast[i][1]+wast[i][2];
052.
}
053.
if (value[i][0] == 3)
054.
{
055.
int t_4 = value[i][2];
056.
value[i][2]+= value[i][1];
057.
wast[i][2]+= wast[i][1];
058.
value[i][3]+= value[i][1];
059.
wast[i][3]+= wast[i][1];
060.
value[i][0]++;
061.
wast[i][0]++;
062.
value[i][4] = value[i][3]+value[i][2]-value[i][1];
063.
wast[i][4] = wast[i][3]+wast[i][2]-wast[i][1];
064.
}
065.
}
066.
/*cout<<flag<<endl;
067.
for (int i=1;i<=flag;i++)
068.
{
069.
for (int j=1;j<=value[i][0];j++)
070.
{
071.
cout<<value[i][j]<<" ";
072.
}
073.
cout<<endl;
074.
}*/
075.
}
076.
077.
int max(int a,int b)
078.
{
079.
return a>b?a:b;
080.
}
081.
082.
void dp()
083.
{
084.
for (int i=0;i<=n;i++)
085.
for (int j=1;j<=flag;j++)
086.
for (int k=1;k<=value[j][0];k++)
087.
{
088.
if (i - wast[j][k] < 0)
089.
{f[i][j] = f[i][j-1];
090.
continue;
091.
}
092.
int temp=f[i][j-1];
093.
f[i][j] = max(f[i-wast[j][k]][j-1] + value[j][k],f[i][j]);
094.
f[i][j] = max(temp,f[i][j]);
095.
ans = max(f[i][j],ans);
096.
}
097.
}
098.
099.
int main()
100.
{
101.
init();
102.
dp();
103.
cout<<ans*10;
104.
return 0;
105.
}