題意：給定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);}} }

總結

以上是生活随笔為你收集整理的uva 1433——Garlands的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。