首页 > 代码库 > hdu-4976-A simple greedy problem.
hdu-4976-A simple greedy problem.
这个题目很不错
首先把小兵的生命值排序,然后我们可以知道,每一个血量值,A只能杀掉一个人。
我们就开始贪心每一个血量,我们把小兵攻击到这个血量需要多少步。
dp[j]:我们当前还剩余j次攻击,杀死的小兵数量,
从1到最大小兵血量枚举。
#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define LL long long
#define lcm(a,b) (a*b/gcd(a,b))
//O(n)求素数,1-n的欧拉数
#define N 1500001
int a[1100];
int b[1100];
int c[1100];
int dp[1100];
int main()
{
int T;
int cas=0;
cin>>T;
int n;
while(T--)
{
cas++;
scanf("%d",&n);
int m=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
m=max(a[i],m);
}
sort(a+1,a+n+1);
memset(c,0,sizeof(c));
for(int i=1; i<=n; i++)
{
int j=a[i];
while(c[j]&&j>0)j--;
if(j!=0)b[j]=a[i]-j;
c[j]=1;
}
memset(dp,0,sizeof(dp));
int maxx=-1;
for(int i=1; i<=m; i++)
{
for(int j=i;j>=1;j--)dp[j]=dp[j-1];
for(int j=0;j<=i;j++)
{
if(j>b[i]&&c[i])dp[j-b[i]-1]=max(dp[j-b[i]-1],dp[j]+1);
}
}
for(int j=0;j<=m;j++)maxx=max(maxx,dp[j]);
printf("Case #%d: %d\n",cas,maxx);
}
return 0;
}
hdu-4976-A simple greedy problem.