DP训练7 重新复健

很久没写题了 大概有半个月吧 中间有许多忙事
然后这几天开学也是 手机坏掉了 电脑坏掉了 然后又要招新
最重要的是 复健 ccpc今年去不了了 因为报名没注意过时间了

第一道错排题目

做了这道题 我才知道错排的 首先错排是什么
就是说 a b c d....这么多个人 没有一个人可以站在各自的位置上
这个方案书 可以通过数学公式求出来
假设现在我们有n个元素 第n个元素放在一个位置上有n-1种放法对吧
对于这个位置k来说 这个元素k可以放在n 也可以不放 想象以下 你吃我的
我可以吃回 也可以不吃回对吧

于是有fn=（n-1）*（fn-2+fn-1） 特别的 f1=0 f2=1
下面是改编 我差点以为也是错排了

这题

第二个

当时看来一眼题目数据范围 以为dp d了半天做不出来
猜猜是什么算法

一道很好的数学dp题

这道题蛮难的

对于一个ax的拆分 他可以给前一个人的x或者y进行配对
所以有4种配对方式 我们每次都要取出最小的情况

还要考虑一个事情 就是这个拆分的数字是多少

一个数x 拆分相乘最大就是拆分的两个数字相差最小，反之，则最小

于是 我们就可以知道拆分的数字了

那么问题来了 怎么求拆分的数字 题目说了

（x-s）*（y-s）>=0 要求了 必须 两个人必须都大于或者小于s 或者至少有一个等于s
我们要对这个ax进行枚举分析
如果说这个ax很大的话 我们要拆分出极差最大的两个数 肯定是一个为s 一个为ax-s
如果ax很小的话 注意都是非负整数 两个数极差最大 肯定是一个为0 一个直接为ax了

那如果说ax恰好处于中间呢 那这个中间是什么意思呢 其实就是说大于s小于2s这种情况
这种拆分我们不能让一个数大于s 一个数小于的 这种时候想让他满足条件 我们只能让一方为s 另一方取差值 这是最优分配了 两个人都小于s 肯定不是最优的极差
于是就写出来了

	for(int i=2;i<=n-1;i++){
		cin>>a[i];	
		if(a[i]>=2*s){
			mini[i]=s;maxn[i]=a[i]-s;
		}
		else {
			mini[i]=max(0*1LL,a[i]-s);
			//不可以直接定义maxn=s
			maxn[i]=a[i]-mini[i];
		}
	}

然后注意一个dp书写 由于有4种配对方式
分别是前一个大配小大 或者前一个小配小大 于是开二维就行了

		dp[i][0]=min(dp[i-1][0]+maxn[i-1]*mini[i],dp[i-1][1]+mini[i-1]*mini[i]);
		dp[i][1]=min(dp[i-1][0]+maxn[i-1]*maxn[i],dp[i-1][1]+mini[i-1]*maxn[i]);

于是这题就写出来了 真有点难的