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

· · 题解

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

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

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

code

#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;
}