网站服务器租用方法,网站模板开发平台怎么做,免费做网站软件视频,上海的装修公司排名题意#xff1a;给定n个值#xff0c;然后把这n个值分为m-1段#xff0c;每段的一半长度不超过k#xff0c;求分得的的段中#xff0c;最大的半段的最小值。 思路#xff1a;二分dp#xff0c;dp#xff08;i#xff0c;0#xff09;表示前i个不超过x的最小段数…题意给定n个值然后把这n个值分为m-1段每段的一半长度不超过k求分得的的段中最大的半段的最小值。 思路二分dpdpi0表示前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 bitsetusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;const int INF0x3fffffff;
const int inf-INF;
const int N1000000;
const int M40005;
const int mod1000000007;
const double piacos(-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 is;in;i)
#define lson l,m,rt1
#define rson m1,r,rt1|1
#define lrt rt1
#define rrt rt1|1
#define middle int m(rl)1
#define lowbit(x) (x-x)
#define pii pairint,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 i2;in;i2){dp[i][0]dp[i][1]INF;for (int j1;jki-2*j0;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,vi);s[i]s[i-1]v[i];}if ((n1)||n2*(m-1)||nk*2*(m-1)) puts(BAD);else{int l1,rs[n];while (lr){int mid(rl)1;if (ok(mid)) rmid;else lmid1;}printf(%d\n,l);}}
}
