题解：P13316 [GCJ 2012 #1A] Kingdom Rush

很容易想到一个贪心思路：把一星要的星星和二星的分开升序排序，然后从前往后通二星，星星不够就从前往后通一星，直到星星够。

但这是错的，因为通了一星之后，二星不能拿到两个星，只能拿一个，然后就需要通更多一星。

所以考虑尽可能多的关卡是直接通二星。所以在通一星补星的时候如果有多个可以通的关卡，则优先选择其二星门槛高的（因为门槛越高越后面才会过）。

code

CPP

#include<bits/stdc++.h>
using namespace std;
int a[101],sum[10001];
bool b[100001];
int main(){
	memset(sum,0x3f,sizeof(sum));
	int l,s,t,m;
	cin>>l>>s>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	sort(a,a+m+2);
	int sum1=0;
	for(int i=1;i<=m+1;i++){
		if(a[i]-a[i-1]<=t*s){
			sum1+=a[i]-a[i-1];
		}
		else{
			sum1+=(a[i]-a[i-1])%t+t;
		}
		b[sum1]=true;
	}
	sum[0]=0;
	for(int i=1;i<=sum1+t;i++){
		for(int j=s;j<=t;j++){
			if((i-j)>=0){
				sum[i]=min(sum[i],sum[i-j]+b[i]);
			}
		}
	}
	int ans=INT_MAX;
	for(int i=sum1;i<=sum1+t;i++){
		ans=min(ans,sum[i]);
	}
	cout<<ans;
}

题解：P13316 [GCJ 2012 #1A] Kingdom Rush

文章操作

code

相关推荐

评论

题解：P13316 [GCJ 2012 #1A] Kingdom Rush