【题解】Codeforces Round #608 (Div. 2) D. Portals

作者： 作者的头像   Alier ,  2019-12-16 14:02:03 ,  所有人可见 ,  阅读 984

2


http://codeforces.com/contest/1271/problem/D

//主要思路，求前缀和,算出每个点可以扔掉的兵（如果前面某个点扔掉了兵，后面所有点都只能少扔一个）
//两个贪心
//1.每个点的扔点位置尽量靠后，因为可以保留战力
//2.从分数最大的开始扔起，把有限的扔兵机会让给大的分数

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5010;
int n,m,k;
int a[N],b[N],c[N];//攻破所需人数，获得人数，奖励得分
int l[N],d[N],f[N],h[N];//可以扔掉兵攻占i的最晚的点，累加到i的上限兵人数,这个点可以扔掉的兵数
int idx[N];
int ans;

//看看这题有没有解，顺便求个前缀和：d[i]=b[1]+...+b[n]
bool check()
{
    int p=k;
    for(int i=1;i<=n;i++)
    {
        if(p<a[i]) return 1;
        p+=b[i],d[i]=p;//d[i]累加到i点为止的上限兵人数
    }
    return 0;
}

//重载运算符
bool cmp(const int &a,const int &b){
    return c[a]>c[b];

}

//判断这个点能不能扔兵
bool check2(int x)
{
    for(int i=n;i>=x;i--){
        if(h[i]==0) return 0;//如果后面有个点开始不能扔兵的话这个点也不能扔兵
    }
    return 1;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        l[i]=i,idx[i]=i;//初始化idx，以及扔兵位置
    }

    //读入每个portal最晚在哪里扔下
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        l[y]=max(l[y],x);
    }

    //判断题目是否有解
    if(check()){
        puts("-1");
        return 0;
    }

    //计算到这个点可以扔的兵数
    a[n+1]=0;
    for(int i=1;i<=n;i++){
        h[i]=d[i]-a[i+1];
    }


    sort(idx+1,idx+1+n,cmp);//把攻占分数从大到小排序

    for(int i=1;i<=n;i++)
    {
        int x=idx[i];//从大到小取出队头
        if(check2(l[x])){    //能扔的话，把每个点的上限扔兵数都减去1
            for(int j=l[x];j<=n;j++) h[j]--;
            ans+=c[x];
        }
    }

    printf("%d\n",ans);
    return 0;
}

3 评论

用户头像
qTWTq   2019-12-17 15:20         踩      回复

我也来发个dp做法,贪心什么的太难了qwq

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
const int M = 10010;
int f[2][N];
int h[N],e[M],ne[M],idx;
struct node{
    int a,b,c;
};
node arr[N];
int mo[N];
int hr[N],hl[N];
int tep_s[N];
int cnt = 0;
// 当前在第i个castle,现在手上有多少个士兵,这里的士兵不包括接下来会送出去的士兵
// 对于某个点来说,我只有当到达能走到它的所有后续点中坐标最大的才往这点走,
// 这一步是贪心
// 然后对于所有点就是nlogn + n * n
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
bool cmp(int a,int b)
{
    return a > b;
}
int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    memset(f,-0x3f,sizeof f);
    f[0 & 1][k] = 0;
    for(int i = 1;i <= n;i ++)
    {
        cin >> arr[i].a >> arr[i].b >> arr[i].c;
    }
    // mo表示在到达第i个castle时最多能有多少士兵,mo[i] <= 5000
    mo[1] = k;
    for(int i = 1;i <= n;i ++)
    {
        mo[i + 1] = arr[i].b + mo[i];
    }
    // 对每一个a记录一个最大的b
    int x,y;
    for(int i = 1;i <= m;i ++)
    {
        cin >> y >> x;
        hr[x] = max(hr[x],y);
    }
    memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i ++)
    {
        if(hr[i]){
            add(hr[i],i);
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        cnt = 0;
        if(!hr[i])tep_s[++ cnt] = arr[i].c;
        for(int j = h[i];j != -1;j = ne[j])
        {
            tep_s[++ cnt] = arr[e[j]].c;
        }
        sort(tep_s + 1,tep_s + cnt + 1,cmp);
        for(int j = 1;j <= cnt;j ++)tep_s[j] += tep_s[j - 1];
        for(int j = 0;j < N;j ++)
        {
            f[i & 1][j] = -0x3f3f3f3f;
        }
        for(int j = 0;j <= mo[i];j ++)
        {
            if(j >= arr[i].a && f[i - 1 & 1][j] >= 0){
                f[i & 1][j + arr[i].b] = f[i - 1 & 1][j];
                for(int k = 1;k <= cnt;k ++)
                {
                    f[i & 1][j + arr[i].b - k] = max(f[i & 1][j + arr[i].b - k],f[i & 1][j + arr[i].b] + tep_s[k]);
                }
            }
        }
    }
    int ans = -1;
    for(int i = 0;i < N;i ++)ans = max(ans,f[n & 1][i]);
    cout << ans << endl;
}
用户头像
byene   2019-12-18 01:32         踩      回复

dp的前提条件也有个贪心的过程吧。就是越后面越优。这点卡死了T_T

用户头像
qTWTq   2019-12-18 10:21    回复了 byene 的评论         踩      回复

嗯