Question

杭电ACM2191，我的代码错哪了，为啥WA？

#include <stdio.h>
int main(void)
{
int i,C,j,m,n,t,s,p[110],h[110],c[110];
scanf("%d",&C);
while(C--)
{
scanf("%d%d",&n,&m);
if(n<=0&&n>100&&m<=0&&m>100) break;
for(i=1;i<=m;i++)
scanf("%d%d%d",&p[i],&h[i],&c[i]);
for(i=1;i<=m;i++)
for(j=i+1;j<=m;j++)
if(p[i]>p[j])
{
t=p[i];p[i]=p[j];p[j]=t;
t=h[i];h[i]=h[j];h[j]=t;
t=c[i];c[i]=c[j];c[j]=t;
}
s=0;
for(i=1;i<=m;i++)
{
if(n-p[i]*c[i]>0)
{
s+=h[i]*c[i];
n=n-p[i]*c[i];
}
else
{
s+=n/p[i]*h[i];
break;
}
}
printf("%d\n",s);
}
return 0;
}

Answer 1

楼主用的是贪心吧。。
你橘哪的算法错了，
这题大米不能分割，所以不能用贪心。
这题得用背包。如果不会的话，可以去百度搜下资料。。

我的AC代码。凳迹。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 1005
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
int dp[N][N];
int main()
{
int t;
int i,j,k,am,a;
int n,m;
int max;
int vol[N],val[N],nn[N];
cin>>t;
while(t--)
{
cin>>m>>n;
for(i=1;i<=n;i++)
cin>>vol[i]>>val[i]>>nn[i];
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=m;j>=0;j--)
{
max=-1;
for(k=0;k<=nn[i]&&k*vol[i]<=j;k++)
max=Max(max,dp[i-1][j-k*vol[i]]+k*val[i]);
dp[i][j]=max;
}
cout<圆粗码<dp[n][m]<<endl;

}
return 0;
}

Answer 2

#include<stdio.h>
#include<string.h>
void main()
{
char s[51];
int m,i,j,n,t;
while(scanf("%d%*c"模颤,&m)==1)
{
for(i=0;i<旦哗败m;i++)
{
gets(s);
n=strlen(s);
if(n<8 || n>16)
{
printf("NO\芦搭n");
continue; // 粗心大意啊，应该是continue的说
}
else
{
t=0;
for(j=0;j<n;j++)
{
if((s[j]>='a') && (s[j]<='z'))
{
t++;
break;
}
}
for(j=0;j<n;j++)
{
if((s[j]>='A') && (s[j]<='Z'))
{
t++;
break;
}
}
for(j=0;j<n;j++)
{
if((s[j]>='0') && (s[j]<='9'))
{
t++;
break;
}
}
for(j=0;j<n;j++)
{
if((s[j]=='~') || (s[j]=='!') || (s[j]=='@') || (s[j]=='#') || (s[j]=='$') || (s[j]=='%') || (s[j]=='^'))
{
t++;
break;
}
}
if(t<3)
printf("NO\n");
else
printf("YES\n");
}

}
}
}

追问

你搞错题目了吧