首页 > 代码库 > A simple greedy problem(hdu 4976)
A simple greedy problem(hdu 4976)
题意:有n个小兵,每个小兵有a【i】血量,第一个人每次只能对一个小兵砍一滴血,第二个人每次对所有生存的小兵砍一滴血。
最后看第一个人最多可以砍杀几个小兵。
/* 首先,如果所有小兵的血量都不同的话,我们可以杀死所有的小兵,如果所以我们应该尽量使小兵血量不同, 也就是在不能将某个小兵一击致命的情况下,对某个某个血量相同的小兵砍一刀,使其血量不同。 预处理出c[i]表示i血量这个位置上的小兵是由c[i]血量的小兵砍过来的。 dp[i][j]表示进行了i轮之后,留有的砍兵机会为j次的最大值。 dp[i][j]=max(dp[i-1][j-1],dp[i-1][j+c[i]-i]) */ #include<iostream> #include<cstdio> #include<cstring> #define N 1010 using namespace std; int c[N],d[N],dp[N][N],s[N],n,m,top,cas; int main(){ int T;scanf("%d",&T); while(T--){ m=0,top=0; memset(d,0,sizeof(d)); memset(c,0,sizeof(c)); memset(dp,0,sizeof(dp)); scanf("%d",&n); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); d[x]++;m=max(m,x); } for(int i=1;i<=m;i++){ if(d[i]==1) c[i]=i; else if(d[i]==0) s[++top]=i; else { c[i]=i; while(top&&d[i]>1){ int x=s[top]; if(i-x<=top){ top--; c[x]=i; d[i]--; } else break; } } } for(int i=1;i<=m;i++) for(int j=0;j<=i;j++){ if(j) dp[i][j]=dp[i-1][j-1]; if(c[i]&&j+c[i]-i<i) dp[i][j]=max(dp[i][j],dp[i-1][j+c[i]-i]+1); } int ans=0; for(int i=0;i<=m;i++) ans=max(ans,dp[m][i]); printf("Case #%d: %d\n",++cas,ans); } return 0; }
A simple greedy problem(hdu 4976)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。