本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-05 09:38:47

题目大意； 某国一个礼拜有$N$ 天。国王高桥准备把每一天安排为 节假日或者工作日。如果$i$号是工作日，那么动力是 $min(x,y)$，其中 $x$ 和 $y$ 是它离前一个或后一个节假日的天数。分配休息日，求出每周$N$天的生产值之和最大可以是多少。

拿到题目，感觉无从下手。
先枚举，假设只有1天休息，就枚举是哪天休息。
根据题意，只与距离前后休息的天数有关。与具体哪天休息无关。
$。。。。。。 16，25，43，34，52，61 ，$ 设一段工作日为$m$，那么$s=2\sum a\frac m 2 $
$。。。。。15，24，33，42，51 $奇数偶数不同。
可以统计出$1...n$连续工作时间的效率值$s_i$。
设每段背包状态为$。。。* $。
设定第一天为休息日。做完全背包 背包总体积为$n；1（.。。） （。。。）$最后一个和第一个*重合 有n-1个物品， 体积为1到n，价值为s0到sn-1 细节处理，要和开头环起来，

1：0
2：11          a1         
3  12 21       2a1
4 13 22 31     2a1+a2
5 14 23 32 41  2a1+2a2
6              2a1+2a2+a3
7              2a1+2a2+2a3

- 参考代码

#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+9; 
ll n,a[N],w[N],f[N]; 

int main(){

	cin>>n;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++){\/\/..*  i包含结尾休息日 	
		w[i]=w[i-1]+a[i\/2];
	}
	memset(f,-32,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){\/\/物品 
		for(int j=i;j<=n;j++){\/\/背包体积
		 	f[j]=max(f[j],f[j-i]+w[i]) ;
			
		}
	}
	cout<<f[n]<<endl;	
}