题解 CF1012C 【Hills】

ouuan

2018-07-31 09:26:20

Solution

这里是双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; } ```