Mudrobøt @ 2018-02-04 09:08:34
此代码本机运行第十个点是对的,在洛谷IDE上运行第十个点也是RE的打不出答案,但是本机可以打出来! 下面是代码:
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
struct sd{
int weight,value;
bool prime;
}thing;
int M[32005];
int num=0;
bool judger[32005];
vector<sd> subject[80];
vector<sd> group[80];
int m,n;
void init();
int main()
{
init();
int limit=0;
for(int i=1;i<=num;++i)
{
for(int k=limit;k>=0;--k)
{
for(int j=group[i].size()-1;j>=0;--j)
{
if((k==0||M[k]!=0)&&k+group[i][j].weight<=m)
{
if(!judger[k]&&M[k+group[i][j].weight]<M[k]+group[i][j].value)
{
M[k+group[i][j].weight]=M[k]+group[i][j].value;
judger[k+group[i][j].weight]=true;
}
}
if(k+group[i][j].weight>limit)
limit=k+group[i][j].weight;
}
}
memset(judger,false,sizeof(judger));
}
long long ans=0;
for(int i=0;i<=m;++i)
if(ans<M[i])
ans=M[i];
cout<<ans;
return 0;
}
void init()
{
int a,b;
int c;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&a,&b,&c);
thing.value=a*b;
thing.weight=a;
if(c==0)
{
thing.prime=true;
subject[i].push_back(thing);
}
else
{
thing.prime=false;
subject[c].push_back(thing);
}
}
for(int i=1;i<=n;++i)
{
if(subject[i].size()==0)
continue;
else
{
num++;
if(subject[i].size()==1)
{
group[num].push_back(subject[i][0]);
}
else if(subject[i].size()==2)
{
int king;
if(subject[i][0].prime) king=0; else king=1;
group[num].push_back(subject[i][king]);
sd change;
change.weight=subject[i][king].weight+subject[i][1-king].weight;
change.value=subject[i][king].value+subject[i][1-king].value;
group[num].push_back(change);
}
else if(subject[i].size()==3)
{
int king;
if(subject[i][0].prime) king=0; else if(subject[i][1].prime) king=1; else king=2;
group[num].push_back(subject[i][king]);
sd swp;
swp=subject[i][king];
subject[i][king]=subject[i][0];
subject[i][0]=swp;
sd change;
change.weight=subject[i][0].weight+subject[i][1].weight;
change.value=subject[i][0].value+subject[i][1].value;
group[num].push_back(change);
change.weight=subject[i][0].weight+subject[i][2].weight;
change.value=subject[i][0].value+subject[i][2].value;
group[num].push_back(change);
change.weight=subject[i][0].weight+subject[i][1].weight+subject[i][2].weight;
change.value=subject[i][0].value+subject[i][1].value+subject[i][2].value;
group[num].push_back(change);
}
}
}
}
by fbhou @ 2018-02-07 08:41:36
@eternal风度 这样说吧我跟他基本可以随便开玩笑 是吧@Mudrobot
by eternal风度 @ 2018-02-07 14:04:16
@fbhou ?
by fbhou @ 2018-02-08 08:43:51
@eternal风度 没想到吧他现在就坐在我旁边
by fbhou @ 2018-02-08 08:44:29
@eternal风度 不要管太多别人的私事
by 飞翔的金鱼 @ 2018-02-08 17:38:17
...
by 飞翔的金鱼 @ 2018-02-08 17:38:58
我RE七个点!!??