uva 1433——Garlands

﹏ヽ暗。殇╰゛Y 2022-08-18 11:32 74阅读 0赞

题意：给定n个值，然后把这n个值分为m-1段，每段的一半长度不超过k，求分得的的段中，最大的半段的最小值。

思路：二分+dp，dp（i，0）表示前i个不超过x的最小段数，该数据不超过m-1就表示可行，01表示奇数和偶数便于转移。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=40005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int T,n,m,k;
    int v[M],s[M];
    int dp[M][2];
    
    int ok(int x){
        dp[0][0]=0;dp[0][1]=INF;
        for (int i=2;i<=n;i+=2){
            dp[i][0]=dp[i][1]=INF;
            for (int j=1;j<=k&&i-2*j>=0;j++){
                if (s[i]-s[i-j]>x) break;
                if (s[i-j]-s[i-2*j]<=x){
                    dp[i][0]=min(dp[i][0],dp[i-2*j][1]+1);
                    dp[i][1]=min(dp[i][1],dp[i-2*j][0]+1);
                }
            }
        }
        if (dp[n][(m-1)%2]>m-1) return 0;
        return 1;
    }
    int main()
    {
        scanf("%d",&T);
        while (T--){
            scanf("%d %d %d",&n,&m,&k);
            s[0]=0;
            ft(i,1,n){
                scanf("%d",v+i);
                s[i]=s[i-1]+v[i];
            }
            if ((n&1)||n<2*(m-1)||n>k*2*(m-1)) puts("BAD");
            else{
                int l=1,r=s[n];
                while (l<r){
                    int mid=(r+l)>>1;
                    if (ok(mid)) r=mid;
                    else l=mid+1;
                }
                printf("%d\n",l);
            }
    
        }
    }