BruceJay's Blog

BZOJ1899 午餐

| Comments

To start with

Bruce随意脑补了一个无脑DP,居然是正解。

Problem

Solution

第一步的贪心策略:吃饭吃得快的后打饭。
然后就DP了。f[i][j]表示前i个人,第一队打饭用了j分钟,所需最短吃饭时间。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 210;
const int INF = 0x3f3f3f3f;
struct node{int x,y;}a[N];
bool cmp(const node& a1,const node& a2)
{return a1.y>a2.y;}
int f[N][N*N]; int sum[N]; int n,ans=INF;

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

int main()
{
    int tmp;
    freopen("lunch.in","r",stdin);
    freopen("lunch.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read(); a[i].y=read();
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].x;
    memset(f,INF,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=sum[i];j++){
        tmp=max(f[i][j],sum[i]-j+a[i+1].x+a[i+1].y);
        f[i+1][j]=min(f[i+1][j],tmp);
        tmp=max(f[i][j],j+a[i+1].x+a[i+1].y);
        f[i+1][j+a[i+1].x]=min(f[i+1][j+a[i+1].x],tmp);
    }
    for(int i=0;i<=sum[n];i++) ans=min(ans,f[n][i]);
    printf("%d",ans); return 0; 
}

Last but not least

TB表示这题很简单。。。
感觉DP的思路不是很自然啊,是不是人太蠢??

Comments

comments powered by Disqus