M_sea

洛谷2577 [ZJOI2005]午餐
Luogu分析当然这题的正解是贪心+DP。DP的题一般可以用随机贪心来做?首先要证出来:如果$x$要排在$y$前面...
扫描右侧二维码阅读全文
01
2018/11

洛谷2577 [ZJOI2005]午餐

Luogu

分析

当然这题的正解是贪心+DP。

DP的题一般可以用随机贪心来做?

首先要证出来:如果$x$要排在$y$前面,那么必须有:

$$A_x+max\left\{B_x,A_y+B_y\right\}<A_y+max\left\{B_y,A_x+B_x\right\}$$

然后随机每一个人放在哪个队里,贪心求解。

跑个10000遍就能过了。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=200+10;

int n;
struct node {
    int a,b;
    bool operator <(const node& rhs) const {
        return a+max(b,rhs.a+rhs.b)<rhs.a+max(rhs.b,a+b);
    }
} a[MAXN];
int s[MAXN];

inline int calc() {
    int ta=0,tb=0,rt=0;
    for (re int i=1;i<=n;i++) {
        if (s[i]==0) ta+=a[i].a,rt=max(rt,ta+a[i].b);
        else tb+=a[i].a,rt=max(rt,tb+a[i].b);
    }
    return rt;
}

int main() {
    srand(19260817);
    n=read();
    for (re int i=1;i<=n;i++) a[i].a=read(),a[i].b=read();
    sort(a+1,a+n+1);
    int ans=2147483647;
    for (re int i=1;i<=10000;i++) {
        for (re int j=1;j<=n;j++) s[j]=rand()%2;
        ans=min(ans,calc());
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 46 PM

发表评论

2 条评论

  1. smy

    请您用随机贪心做状压dp(

    1. M_sea
      @smy

      不会,下一个

      你坠强啦