物灵 @ 2018-04-04 16:29:52
#include <cstdio>
#include <algorithm>
int n, m, c_v[61], c_p[61], v1_v[61], v1_p[61], v2_v[61], v2_p[61], dp[32001];
//v 代表价格，p 代表乘积
//c 为主件，v1 为附件 1，v2 为附件 2
int max_5p(int u, int v, int w, int uu, int vv){
//5 数最大值，某翎承认只是不想打 if
return std::max(u, std::max(v, std::max(w, std::max(uu, vv))));
}
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int t_v, t_p, t_q;
scanf("%d %d %d", &t_v, &t_p, &t_q);
//当前读入的 3 值
if(t_q) //附件
if(v1_v[t_q]) v2_v[t_q] = t_v, v2_p[t_q] += t_v*t_p; //附件 2
else v1_v[t_q] = t_v, v1_p[t_q] = t_v*t_p; //附件 1
else c_v[i] = t_v, c_p[i] = t_v*t_p; //主件
}
for(int i=1; i<=m; i++)
if(c_v[i])
for(int j=n; j>=c_v[i]; j--)
dp[j] = max_5p(dp[j], dp[j-c_v[i]] + c_p[i], //什么都不要和只要主件
v1_v[i] && v1_v[i]+c_v[i]<=j ? dp[j-c_v[i]-v1_v[i]]+c_p[i]+v1_p[i] : -1, //要附件 1
v2_v[i] && v2_v[i]+c_v[i]<=j ? dp[j-c_v[i]-v2_v[i]+c_p[i]]+v2_p[i] : -1, //要附件 2
v1_v[i] && v2_v[i] && v1_v[i]+v2_v[i]+c_v[i]<=j ? dp[j-c_v[i]-v1_v[i]-v2_v[i]]+c_p[i]+v1_p[i] + v2_p[i] : -1); //要附件 1 和 2
printf("%d", dp[n]);
return 0;
}by aface0427 @ 2018-04-04 16:47:55
丑死了
by 曹老师 @ 2018-04-04 17:19:41
下划线什么的好难受
by 轻尘 @ 2018-04-18 20:55:25
// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
inline int read()
{
int x = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9')
{
x = x*10 + c-'0';
c = getchar();
}
return x;
}
inline void print(int x)
{
if(x>9)
print(x/10);
putchar(x%10+'0');
}
struct s
{
int v,w,t1,t2,tag;
}a[100];
int f[32000];
int main()
{
int n = read(), m = read();
for(int i=1;i<=m;i++)
{
a[i].v = read(),a[i].w = read();
int team = read();
if(team>0)
{
a[team].t1>0?a[team].t2 = i:a[team].t2 = i;
a[i].tag = 2;
}
}
for(int i=1;i<=m;i++)
for(int j=n;j>=a[i].v;j--)
{
if(a[i].tag == 2) continue;
if(!a[i].t1)
f[j] = max(f[j-a[i].v]+a[i].w*a[i].v,f[j]);
if(!a[i].t2&&j-a[i].v-a[a[i].t1].v>=0)
f[j] = max(f[j],
max(f[j-a[i].v] + a[i].v * a[i].w ,
f[j-a[i].v-a[a[i].t1].v]+a[i].w *a[i].v+a[a[i].t1].v *a[a[i].t1].w));
else if(j-a[i].v-a[a[i].t1].v-a[a[i].t2].v>=0)
f[j] = max(f[j],
max(f[j-a[i].v] + a[i].v * a[i].w,
max(f[j-a[i].v-a[a[i].t1].v]+a[i].v*a[i].w+a[a[i].t1].w*a[a[i].t1].v,
f[j-a[i].v-a[a[i].t1].v-a[a[i].t2].v]+a[i].v*a[i].w+a[a[i].t1].v*a[a[i].t1].w+a[a[i].t2].v*a[a[i].t2].w)));
}
print(f[n]);
return 0;
}
by 轻尘 @ 2018-04-18 20:57:07
同为30分 ：（
by VPYEKINDAR @ 2018-04-22 22:20:57
···
using namespace std;
struct p{
int m,v;
int shu,extra[3],value[3],num;
}node[61];
int n,m;
int dp[32000];
int main()
{
int qe,e,f;
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&qe,&e,&f);
node[i].num=f;
if(!f){
node[i].m=qe;
node[i].v=qee;}
if(f){
node[f].shu++;
node[f].extra[node[f].shu]=qe;
node[f].value[node[f].shu]=qee;
}
}
int j;
for(i=1;i<=m;i++)
{
if(!node[i].num){
for(j=n;j>=1;j--)
{
if(j>=node[i].m)
dp[j]=max(dp[j],dp[j-node[i].m]+node[i].v);
if(node[i].shu==1&&node[i].m+node[i].extra[1]<=j)
dp[j]=max(dp[j],dp[j-node[i].m+node[i].extra[1]]+node[i].v+node[i].value[1]);
if(node[i].shu==2)
{
if(node[i].m+node[i].extra[1]+node[i].extra[2]<=j)
dp[j]=max(dp[j],dp[j-node[i].m+node[i].extra[1]+node[i].extra[2]]+node[i].v+node[i].value[1]+node[i].value[2]);
if(node[i].m+node[i].extra[1]<=j)
dp[j]=max(dp[j],dp[j-node[i].m+node[i].extra[1]]+node[i].value[1]+node[i].v);
if(node[i].m+node[i].extra[2]<=j)
dp[j]=max(dp[j],dp[j-node[i].m-node[i].extra[2]]+node[i].v+node[i].value[2]);
}
}}
}
cout<<dp[n];
} ···
by VPYEKINDAR @ 2018-04-22 22:21:35
#include <bits/stdc++.h>
using namespace std;
struct p{
int m,v;
int shu,extra[3],value[3],num;
}node[61];
int n,m;
int dp[32000];
int main()
{
int qe,e,f;
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&qe,&e,&f);
node[i].num=f;
if(!f){
node[i].m=qe;
node[i].v=qe*e;}
if(f){
node[f].shu++;
node[f].extra[node[f].shu]=qe;
node[f].value[node[f].shu]=qe*e;
}
}
int j;
for(i=1;i<=m;i++)
{
if(!node[i].num){
for(j=n;j>=1;j--)
{
if(j>=node[i].m)
dp[j]=max(dp[j],dp[j-node[i].m]+node[i].v);
if(node[i].shu==1&&node[i].m+node[i].extra[1]<=j)
dp[j]=max(dp[j],dp[j-node[i].m+node[i].extra[1]]+node[i].v+node[i].value[1]);
if(node[i].shu==2)
{
if(node[i].m+node[i].extra[1]+node[i].extra[2]<=j)
dp[j]=max(dp[j],dp[j-node[i].m+node[i].extra[1]+node[i].extra[2]]+node[i].v+node[i].value[1]+node[i].value[2]);
if(node[i].m+node[i].extra[1]<=j)
dp[j]=max(dp[j],dp[j-node[i].m+node[i].extra[1]]+node[i].value[1]+node[i].v);
if(node[i].m+node[i].extra[2]<=j)
dp[j]=max(dp[j],dp[j-node[i].m-node[i].extra[2]]+node[i].v+node[i].value[2]);
}
}}
}
cout<<dp[n];
} by 邓超8888888 @ 2018-06-11 17:18:54
#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 100
#define maxnn 32010
using namespace std;
int size=0,f[maxnn],w[maxn],v[maxn];
bool vis[maxn];
struct node
{
int w1,v1,w2,v2,num;
}e[maxn];
int main()
{
int n,m,q;
memset(vis,false,sizeof(vis));
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&w[i],&v[i],&q);
if(q==0)
{
vis[i]=true;
continue;
}
else if(e[q].num==0)
{
e[q].w1=w[i];
e[q].v1=v[i];
e[q].num++;
}
else
{
e[q].w2=w[i];
e[q].v2=v[i];
e[q].num++;
}
}
for(int i=1;i<=m;i++)
{
if(vis[i]==false) continue;
for(int j=n;j>=0;j--)
{
if(j-w[i]>=0)
{
f[j]=max(f[j],f[j-w[i]]);
f[j]=max(f[j],f[j-w[i]]+w[i]*v[i]);
}
if(e[i].num>=1&&j-w[i]-e[i].w1>=0)
{
f[j]=max(f[j],f[j-w[i]-e[i].w1]+w[i]*v[i]+e[i].w1*e[i].v1);
}
if(e[i].num>=2)
{
if(j-w[i]-e[i].w2>=0)
f[j]=max(f[j],f[j-w[i]-e[i].w2]+w[i]*v[i]+e[i].w2*e[i].v2);
if(j-w[i]-e[i].w1-e[i].w2>=0)
f[j]=max(f[j],f[j-w[i]-e[i].w1-e[i].w2]+w[i]*v[i]+e[i].w2*e[i].v2+e[i].w1*e[i].v1);
}
}
}
printf("%d",f[n]);
return 0;
}