2018.08.19 NOIP模拟 dp(二分+状压dp)

时间:2023-12-14 18:05:14

Dp

题目背景

SOURCE:NOIP2015-SHY-10

题目描述

一块土地有 n 个连续的部分,用 H[1],H[2],…,H[n] 表示每个部分的最初高度。有 n 种泥土可用,他们都能覆盖连续的 k 个部分,第 i 种泥土的价格为 C[i],可以使 i,i+1,…,i+k-1 部分的高度增加 E[i](如果 i+k>n,那就覆盖 i,…,n ),我们必须满足以下条件:

1、每种泥土只能使用一次。

2、成本必须小于等于 m 。

要求在上述条件下,使得最低的部分的高度尽量高,请求出这个高度。

输入格式

第一行三个整数 n,m,k,表示土地有几个部分,最大预算成本以及每种泥土能覆盖的部分数。

接下来 n 行,每行三个整数 H[i],E[i],C[i]。

输出格式

输出一个整数,表示在满足条件的情况下,最低部分的高度的最大值。

样例数据 1

输入

4 20 1

1 3 5

1 7 3

4 6 9

3 5 13

输出

3

备注

【数据范围】

对 30% 的输入数据:1≤n≤20 。

对 100% 的输入数据:1≤k≤11;1≤n≤100;0≤m;H[i],E[i],C[i]≤10^6 。

一看题就知道要二分,关键在于怎么check(考试的时候没想出来)。

本来想写个搜索骗个分的,结果发现有点慢,就换了个贪心+搜索,仍然只有30pts233,虽然得分点跟别人不一样。。。

所以说整体思路就出来了,二分答案,然后状压每个人的前k个人的选取情况转移就行了,如果最后在满足所有人都大于mid的情况下总花费最小值是不超过m的说明情况合法。

代码:

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
int n,m,k,h[105],e[105],c[105],sum[105][2050],l=0x3f3f3f3f,r,mk,f[105][2050],bit[15],ans;
inline bool check(int mid){
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;++i){
        int pos=min(k,i),up=bit[pos];
        bool ff=false;
        for(int j=0;j<up;++j){
            if(sum[i][j]+h[i]<mid)continue;
            f[i][j]=min(f[i][j],f[i-1][(j>>1)]+(j&1?c[i]:0));
            f[i][j]=min(f[i][j],f[i-1][((j>>1)|bit[pos-1])]+(j&1?c[i]:0));
            if(f[i][j]>m)f[i][j]=0x3f3f3f3f;
            else ff=true;
        }
        if(!ff)return false;
    }
    for(int i=0;i<=mk;++i)if(f[n+1][i]<=m)return true;
    return true;
}
int main(){
    n=read(),m=read(),k=read();
    int pos,up;
    for(int i=0;i<=k;++i)bit[i]=1<<i;
    for(int i=1;i<=n;++i){
        h[i]=read(),e[i]=read(),c[i]=read(),pos=min(k,i),up=bit[pos];
        for(int j=0;j<up;++j){
            for(int t=0;t<pos;++t)
                sum[i][j]+=(j&bit[t]?e[i-t]:0);
        }
    }
    l=0,r=1000000005;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid))l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}