题解 CF1012C 【Hills】
ouuan
2018-07-31 09:26:20
这里是双div最优解31ms0KB!
## 赛时心路历程(只想看正解的可以跳过)
首先看这道题感觉貌似可以dp,然后看数据范围,应该是O(n²),因为要求多个k的答案,其中一维肯定是使几个数满足条件,另一维就肯定是算到第几个数了。尝试用f[i][j]代表前i个数有j个满足条件最少操作数,但转移时会因前一个数有没有满足条件而改变,所以尝试用f[i][j][0]表示前i个数有j个满足条件、i不满足条件的最少操作数,f[i][j][1]表示前i个数有j个满足条件、i满足条件的最少操作数(这里的操作数都是把i当做最右一个,即不计算对第i+1个数的操作)。然而f[i][j][1]转移时会不清楚i-1有没有已经被操作,有的dalao是用一堆ifelse解决的,然而我觉得既然状态转移和前两个数是否满足条件都有关,不如就在状态中表示前两个数是否满足条件,于是就有了下面的正解:
## 正解
### 状态表示
(这里的操作数都是把i当做最右一个,即不计算对第i+1个数的操作)
1. f[i][j][0]表示表示前i个数有j个满足条件,i、i-1都不满足条件的最少操作数
2. f[i][j][1]表示表示前i个数有j个满足条件,i满足条件的最少操作数
3. f[i][j][2]表示表示前i个数有j个满足条件,i-1满足条件的最少操作数
都满足条件呢?如果你问这个问题建议你再好好读一读题面...
### 转移方程
```
f[i][j][0]=min(f[i-1][j][0],f[i-1][j][2]);
```
这个没什么说的..
```
f[i][j][1]=min(f[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),f[i-1][j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1));
```
这个分为两种情况:
1. 前两个都不满足条件,那么i-1一定是原来的数,即没有被操作过,需要的操作数就是max(0,a[i-1]-a[i]+1)
2. i-2满足条件,那么i-1已经变成了min(a[i-1],a[i-2]-1),还需要的操作数就是max(0,min(a[i-1],a[i-2]-1)-a[i]+1)
```
f[i][j][2]=f[i-1][j][1]+max(0,a[i]-a[i-1]+1);
```
如果i-1满足条件就只有一种情况,需要的操作数是max(0,a[i]-a[i-1]+1)
### 空间优化
为什么我空间是0KB呢?因为使用了滚动数组(然而这题空间限制512MB,完全不需要滚动数组)
注意到转移只用到了f[i-1][j]和f[i-1][j-1],所以逆序枚举j。
f[i][j][0]转移用到了f[i-1][j][0]和f[i-1][j][2]、f[i][j][1]转移用到了f[i-1][j-1][0]和f[i-1][j-1][2]、f[i][j][2]转移只用到了f[i-1][j][1]。~~进行一个手动拓扑排序~~,就可以得到要先计算0,再计算2,最后计算1。
### 代码
```
#include <iostream>
#include <algorithm>
using namespace std;
int n,f[2510][3],a[5010];
int main()
{
int i,j;
cin>>n;
for (i=1;i<=n;++i)
{
cin>>a[i];
}
for (j=(n+1)/2;j>=0;--j)
{
for (i=0;i<=2;++i)
{
f[j][i]=0x3fffffff; //因为有的状态不存在,比如f[5][4][x],把所有状态初始化为inf就不会让这样的状态被转移,然而inf不能太大,不然加一起会爆int
}
}
f[0][0]=f[1][1]=0; //还是要把f[1][0][0]和f[1][1][1]初始化为0
for (i=2;i<=n;++i)
{
for (j=(i+1)/2;j>=1;--j) //逆序枚举j防止覆盖未转移的状态
{
f[j][0]=min(f[j][0],f[j][2]);
f[j][2]=f[j][1]+max(0,a[i]-a[i-1]+1);
f[j][1]=min(f[j-1][0]+max(0,a[i-1]-a[i]+1),f[j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1));
}
}
for (j=1;j<=(n+1)/2;++j)
{
cout<<min(f[j][0],min(f[j][1],f[j][2]))<<' '; //输出答案
}
return 0;
}
```