UVA - 1443 Garlands (二分+DP)

题意:给你n个数代表重量,让你分成连续的m-1段,每一段的一半长不能超过d,求所有段中,半段最重的最小值

思路:求最大值的最小值,显然是二分的节奏,但这不完全是搜索啊,还有涉及到DP,

那么为了能够用来二分的check,又要用到我们搜索的值,也就是最小值x,如果这n个数能都分成m-1,且按条件不超过x,注意的是其实只要不大于m-1的话都是证明这个数x成立的,所以可以用dp[i][2]表示前i个不超过x的最小段数,只要这个最小的段数不超过m-1,就证明这个是可以的,又增加一维来表示段数是奇偶的情况,便于转移

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 40005;
const int INF = 0x3f3f3f3f;

int w[MAXN],sum[MAXN];
int dp[MAXN][2],n,m,d;

int check(int x){
    dp[0][0] = 0;
    dp[0][1] = INF;
    for (int i = 2; i <= n; i += 2){
        dp[i][0] = INF;
        dp[i][1] = INF;
        for (int len = 1; len <= d && i-2*len >= 0; len++){
            if (sum[i]-sum[i-len] > x)
                break;
            if (sum[i-len] - sum[i-2*len] <= x){
                dp[i][0] = min(dp[i][0],dp[i-2*len][1]+1);
                dp[i][1] = min(dp[i][1],dp[i-2*len][0]+1);
            }
        }
    }
    if (dp[n][(m-1)%2] > m-1)
        return 0;
    else return 1;
}

int main(){
    int t;
    scanf("%d",&t);  
    while (t--){
        scanf("%d%d%d",&n,&m,&d);
        sum[0] = 0;
        for (int i = 1; i <= n; i++){
            scanf("%d",&w[i]);
            sum[i] = sum[i-1] + w[i];
        }
        if ((n & 1) || (n < 2*(m-1)) || (n > 2*d*(m-1)))
            printf("BAD\n");
        else {
            int l = 1,r = sum[n];
            while (l < r){
                int mid = (l+r) >> 1;
                if (check(mid))
                    r = mid;
                else l = mid + 1;
            }
            printf("%d\n",l);
        }
    }
    return 0;
}



UVA - 1443 Garlands (二分+DP)

上一篇:SRM 606 div2 500 EllysNumberGuessing


下一篇:HUST 1328求每一个前缀在串中出现次数和