Refun @ 2017-07-10 11:33:20
#include<iostream>
#include<cstring>
using namespace std;
long long n,m,smax,w[62],c[62],p[62],f[61][3201],fj[62][3][3];
int pd[162];
int main()
{
int i,j,s;
cin>>n>>m;
s=0;
n=n/10;
int x,y,z;
for (i=1;i<=m;++i)
{
cin>>x>>y>>z;
x=x/10;
y=y*x;
if (z==0)
{
++s;
w[s]=x;
c[s]=y;
}
else
{
++pd[z];
fj[z][pd[z]][1]=x;
fj[z][pd[z]][2]=y;
}
}
for (i=1;i<=s;++i)
for (j=n;j>0;--j)
{
if (j-w[i]>=0) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
else
f[i][j]=f[i-1][j];
if (j-w[i]-fj[i][1][1]>=0) f[i][j]=max(f[i][j],f[i-1][j-w[i]-fj[i][1][1]]+c[i]+fj[i][1][2]);
if (j-w[i]-fj[i][2][1]>=0) f[i][j]=max(f[i][j],f[i-1][j-w[i]-fj[i][2][1]]+c[i]+fj[i][2][2]);
if (j-w[i]-fj[i][2][1]-fj[i][1][1]>=0) f[i][j]=max(f[i][j],f[i-1][j-w[i]-fj[i][1][1]-fj[i][2][1]]+c[i]+fj[i][1][2]+fj[i][2][2]);
}
cout<<f[s][n]*10;
}by 宽嫂 @ 2017-07-10 14:28:23
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%!
怒膜褚dalao
by ttgan @ 2017-07-10 16:10:22
我没有看题，不知道怎么做
by 宽嫂 @ 2017-07-10 16:56:59
您看到这句话了吗“每个主件可以有0个、1个或2个附件”
我还以为可以有无穷多个附件....
by 宽嫂 @ 2017-07-10 17:41:01
用记忆化搜索是大概这个样子(然而错了)...
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define max(x,y) ((x)>(y)?(x):(y))
#define MAXM (60+5)
#define MAXN (32000+5)
using namespace std;
struct chu
{
int c;
int q;
int w;
// int bh;
} a[MAXM];
vector<int> v[MAXM];
//bool vis[MAXM];
int f[MAXN];
int ans;
int n;
int m;
//bool v[MAXM];
int dfs(int,int);
/*bool cmp(chu xxx,chu yyyy)
{
return xxx.q<yyyy.q;
}*/
inline int read()
{
int re=0;
char x=0;
while(x<'0'||x>'9')
x=getchar();
while(x>='0'&&x<='9')
{
re*=10;
re+=(x-'0');
x=getchar();
}
return re;
}
int main()
{
// memset(vis,false,sizeof(vis));
memset(f,0,sizeof(f));
n=read();
m=read();
// printf("%d %d",n,m);
// scanf("%d%d",&n,&m);
int srp;
// int dm=m;
for(int i=1; i<=m; i++)
{
v[i].clear();
}
for(int i=1; i<=m; i++)
{
a[i].c=read();
srp=read();
a[i].q=read();
if(a[i].q)
{
v[a[i].q].push_back(i);
}
// scanf("%d%d%d",&a[i].c,&srp,&a[i].q);
a[i].w=srp*a[i].c;
// a[i].bh=i;
}
// sort(a+1,a+m+1,cmp);
ans=dfs(1,n);
for(int i=0; i<=n; i++)
{
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
int dfs(int dq,int mon)
{
if(dq>m)
{
return 0;
}
if(a[dq].q)
{
return dfs(dq+1,mon);
}
else
{
// v[a[dq].bh]=true;
// vis[dq]=true;
if(mon>=a[dq].c)
f[mon]=max(f[mon],(f[mon-a[dq].c]?(f[mon-a[dq].c]+ a[dq].w):(dfs(dq+1,mon-a[dq].c)+a[dq].w)));
if(v[dq].size()>=1&&mon>=(a[v[dq][0]].c+a[dq].c))
f[mon]=max((f[mon-a[v[dq][0]].c-a[dq].c]?f[mon-a[v[dq][0]].c-a[dq].c]:dfs(dq+1,mon-a[v[dq][0]].c-a[dq].c))+a[v[dq][0]].w+a[dq].w,f[mon]);
if(v[dq].size()>=2&&mon>=(a[v[dq][1]].c+a[dq].c))
f[mon]=max((f[mon-a[v[dq][1]].c-a[dq].c]?f[mon-a[v[dq][1]].c-a[dq].c]:dfs(dq+1,mon-a[v[dq][1]].c-a[dq].c))+a[v[dq][1]].w+a[dq].w,f[mon]);
if(v[dq].size()>=2&&mon>=(a[v[dq][0]].c+a[v[dq][1]].c+a[dq].c))
f[mon]=max((f[mon-a[v[dq][1]].c-a[dq].c-a[v[dq][0]].c]?f[mon-a[v[dq][1]].c-a[dq].c-a[v[dq][0]].c]:dfs(dq+1,mon-a[v[dq][1]].c-a[dq].c-a[v[dq][0]].c))+a[v[dq][1]].w+a[dq].w+a[v[dq][0]].w,f[mon]);
// v[a[dq].bh]=false;
// f[dq][mon]=max(f[mon],(f[mon]?f[mon]:dfs(dq+1,mon)));
}
return f[mon];
}循环的话大概是这个样子(对了)...
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define max(x,y) ((x)>(y)?(x):(y))
#define MAXM (60+5)
#define MAXN (32000+5)
using namespace std;
struct chu
{
int c;
int q;
int w;
// int bh;
} a[MAXM];
vector<int> v[MAXM];
//bool vis[MAXM];
int f[MAXN];
int ans;
int n;
int m;
//bool v[MAXM];
int dfs(int,int);
/*bool cmp(chu xxx,chu yyyy)
{
return xxx.q<yyyy.q;
}*/
inline int read()
{
int re=0;
char x=0;
while(x<'0'||x>'9')
x=getchar();
while(x>='0'&&x<='9')
{
re*=10;
re+=(x-'0');
x=getchar();
}
return re;
}
int main()
{
// memset(vis,false,sizeof(vis));
memset(f,0,sizeof(f));
n=read();
m=read();
// printf("%d %d",n,m);
// scanf("%d%d",&n,&m);
int srp;
// int dm=m;
for(int i=1; i<=m; i++)
{
v[i].clear();
}
for(int i=1; i<=m; i++)
{
a[i].c=read();
srp=read();
a[i].q=read();
if(a[i].q)
{
v[a[i].q].push_back(i);
}
// scanf("%d%d%d",&a[i].c,&srp,&a[i].q);
a[i].w=srp*a[i].c;
// a[i].bh=i;
}
// sort(a+1,a+m+1,cmp);
// ans=dfs(1,n);
for(int i=1; i<=m; i++)
{
if(a[i].q)
continue;
for(int j=n; j>=a[i].c; j--)
{
f[j]=max(f[j],f[j-a[i].c]+a[i].w);
if(v[i].size()>=1&&j>=(a[v[i][0]].c+a[i].c))
f[j]=max(f[j],f[j-a[v[i][0]].c-a[i].c]+a[i].w+a[v[i][0]].w);
if(v[i].size()>=2&&j>=(a[v[i][1]].c+a[i].c))
f[j]=max(f[j],f[j-a[v[i][1]].c-a[i].c]+a[i].w+a[v[i][1]].w);
if(v[i].size()>=2&&j>=(a[v[i][0]].c+a[v[i][1]].c+a[i].c))
f[j]=max(f[j],f[j-a[v[i][0]].c-a[v[i][1]].c-a[i].c]+a[i].w+a[v[i][0]].w+a[v[i][1]].w);
}
}
for(int i=0; i<=n; i++)
{
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
/*int dfs(int dq,int mon)
{
if(dq>m)
{
return 0;
}
if(a[dq].q)
{
return dfs(dq+1,mon);
}
else
{
// v[a[dq].bh]=true;
// vis[dq]=true;
if(mon>=a[dq].c)
f[mon]=max(f[mon],(f[mon-a[dq].c]?(f[mon-a[dq].c]+ a[dq].w):(dfs(dq+1,mon-a[dq].c)+a[dq].w)));
if(v[dq].size()>=1&&mon>=(a[v[dq][0]].c+a[dq].c))
f[mon]=max((f[mon-a[v[dq][0]].c-a[dq].c]?f[mon-a[v[dq][0]].c-a[dq].c]:dfs(dq+1,mon-a[v[dq][0]].c-a[dq].c))+a[v[dq][0]].w+a[dq].w,f[mon]);
if(v[dq].size()>=2&&mon>=(a[v[dq][1]].c+a[dq].c))
f[mon]=max((f[mon-a[v[dq][1]].c-a[dq].c]?f[mon-a[v[dq][1]].c-a[dq].c]:dfs(dq+1,mon-a[v[dq][1]].c-a[dq].c))+a[v[dq][1]].w+a[dq].w,f[mon]);
if(v[dq].size()>=2&&mon>=(a[v[dq][0]].c+a[v[dq][1]].c+a[dq].c))
f[mon]=max((f[mon-a[v[dq][1]].c-a[dq].c-a[v[dq][0]].c]?f[mon-a[v[dq][1]].c-a[dq].c-a[v[dq][0]].c]:dfs(dq+1,mon-a[v[dq][1]].c-a[dq].c-a[v[dq][0]].c))+a[v[dq][1]].w+a[dq].w+a[v[dq][0]].w,f[mon]);
// v[a[dq].bh]=false;
// f[dq][mon]=max(f[mon],(f[mon]?f[mon]:dfs(dq+1,mon)));
}
ret…by xMinh @ 2017-07-13 19:56:08
%褚佬