Loi_Anina @ 2018-09-27 20:09:50
RT 大致思路就是分组背包 分组的部分写了两个结构体 代码略丑orz
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int mon;
int b[100];
int ans;
int get;
struct staff
{
int val,pri;
}s[100],all[100];
int imp;
int mas;
int serv[100][10];
int co,num;
struct pack
{
int a,a_b,a_c,a_b_c;
}p[100];
int dp[100][33000];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&s[i].pri,&imp,&mas);
s[i].val=s[i].pri*imp;
if(serv[mas][1]) serv[mas][2]=i;
else serv[mas][1]=i;
if(mas!=0) b[i]=1;
}
for(int i=1;i<=m;i++)
{
// cout<<b[i]<<" ";
if(!serv[i][1])
{
if(!b[i])
{
all[++num].val=s[i].val;
all[num].pri=s[i].pri;
p[++co].a=num;
}
// cout<<i<<" ";
continue;
}
all[++num].val=s[i].val;
all[num].pri=s[i].pri;
p[++co].a=num;
all[++num].val=s[i].val+s[serv[i][1]].val;
all[num].pri=s[i].pri+s[serv[i][1]].pri;
p[co].a_b=num;
if(!serv[i][2]) continue;
all[++num].val=s[i].val+s[serv[i][2]].val;
all[num].pri=s[i].pri+s[serv[i][2]].pri;
p[co].a_c=num;
all[++num].val=s[i].val+s[serv[i][2]].val+s[serv[i][1]].val;
all[num].pri=s[i].pri+s[serv[i][2]].pri+s[serv[i][1]].pri;
p[co].a_b_c=num;
}
// cout<<co;
for(int i=1;i<=co;i++)
for(int j=all[p[i].a].pri;j<=n;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-all[p[i].a].pri]+all[p[i].a].val);
if(j>=all[p[i].a_b].pri) dp[i][j]=max(dp[i][j],dp[i-1][j-all[p[i].a_b].pri]+all[p[i].a_b].val);
if(j>=all[p[i].a_c].pri) dp[i][j]=max(dp[i][j],dp[i-1][j-all[p[i].a_c].pri]+all[p[i].a_c].val);
if(j>=all[p[i].a_b_c].pri) dp[i][j]=max(dp[i][j],dp[i-1][j-all[p[i].a_b_c].pri]+all[p[i].a_b_c].val);
// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
printf("%d",dp[co][n]);
return 0;
}
/*
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
*/
by 小可爱三岁七 @ 2018-09-27 20:14:52
@Anina 提供一组数据
testdata.in
4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10
testdata.out
16700
by 小可爱三岁七 @ 2018-09-27 20:25:56
@Anina 您的#9,#10是数组开小了,把所有数组开大10~100就90了
by Loi_Anina @ 2018-09-27 21:07:50
@小可爱三岁七 啊谢谢
我发现我放错代码了orz
这份确实是可以过90的 转移方程里的判断条件70分的时候写的是> 改成>=就90了
请问这组数据选择的是哪几件物品?
by 小可爱三岁七 @ 2018-09-27 21:13:46
@Anina 其实您数组开大一点就没啥事了qaq
by 小可爱三岁七 @ 2018-09-27 21:14:55
@Anina
我也不知道啊qaq…………你谷主站的数据
我没看这道题qaq(光速逃)
by 小可爱三岁七 @ 2018-09-27 21:15:19
@Anina 而且就是你wa的那个点 #4
by Loi_Anina @ 2018-09-27 21:29:58
@小可爱三岁七 好吧orz
谢谢您
by Loi_Anina @ 2018-09-27 21:50:39
解决了