2151: 种树

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 1706 Solved: 935
[Submit][Status][Discuss]

Description
A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。最终市政府给园林部门提供了m棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上，给出无解信息。

Input
输入的第一行包含两个正整数n、m。第二行n个整数Ai。

Output
输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出“Error!”，不包含引号。

Sample Input
【样例输入1】

7 3

1 2 3 4 5 6 7

【样例输入2】

7 4

1 2 3 4 5 6 7

Sample Output
【样例输出1】

15

【样例输出2】

Error!

恰好选m个，我们可以想到wqs二分。

我们通过减少选的权值，使得我们正好选m个，得到我们的答案。

每次check的时候，我们直接 dp[i][0/1][0/1]表示前i个当中，第1个选没选，第i个选没选的最大价值。

然后如果个数大于等于 m ，那么证明我们减少的权值还不够，那么就增大l即可，否则减少r。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int n,m,a[N],res;
struct node{int val,cnt;}dp[N][2][2],t;
node max(node a,node b){
	return (a.val>b.val||a.val==b.val&&a.cnt>b.cnt)?a:b;
}
int check(int mid){
	memset(dp,0,sizeof dp);
	dp[1][1][1]={a[1]-mid,1};	dp[1][1][0]=dp[1][0][1]={-inf,0};
	for(int i=2;i<=n;i++){
		dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][0][1]);
		dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]);
		dp[i][0][1]={dp[i-1][0][0].val+a[i]-mid,dp[i-1][0][0].cnt+1};
		dp[i][1][1]={dp[i-1][1][0].val+a[i]-mid,dp[i-1][1][0].cnt+1};
	}
	t=max(dp[n][0][0],max(dp[n][0][1],dp[n][1][0]));
	return t.cnt>=m;
}
int wqs(){
	int l=-1e3,r=1e3;
	while(l<=r){
		int mid=l+r>>1ll;
		if(check(mid))	l=mid+1,res=t.val+m*mid;
		else	r=mid-1;
	}
	return res;
}
signed main(){
	cin>>n>>m;	
	for(int i=1;i<=n;i++)	cin>>a[i];
	if(m*2>n)	return puts("Error!"),0;
	cout<<wqs()<<endl;
	return 0;
}