P6304 [eJOI2018] 山

wflengxuenong · 2022-11-07 14:53:33 · 个人记录

/*
dp[i][j][0/1/2]，表示前i个山，建j个房子，
    0:i和i-1都不建，....
    1:i建， (i-1,i)/
    2:i-1建时最小花费。(i-1,i)\

    每种专业都由上一行转移而来，可以滚动优化 
*/
#include<bits/stdc++.h>
using namespace std;
const int N=5009;
int dp[2][N][3],a[N<<1];
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
      cin>>a[i];
  memset(dp,0x3f,sizeof(dp));
  dp[1][0][0]=dp[1][1][1]=0;
  for(int i=2;i<=n;i++){
    for(int j=0;j<=(i+1)/2;j++){
          dp[i&1][j][0]=min(dp[(i-1)&1][j][0],dp[(i-1)&1][j][2]);//i和i-1都没房子，i-2和i-1没有房子，或者 i-1前面有房子 
          dp[i&1][j][2]=dp[(i-1)&1][j][1]+max(0,a[i]-a[i-1]+1);//i-1处有房子，处理房子右侧左侧下降部分的修改值 /
          dp[i&1][j][1]=min(dp[(i-1)&1][j-1][0]+max(0,a[i-1]-a[i]+1),dp[(i-1)&1][j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1));
      //i建房子：        i-2，i-1没有房子，只根据自己修改左侧i-1，              i-2处有房子  ，根据i-2和i修改i-1 
      }
     memset(dp[(i-1)&1],0x3f,12*n+12) ;
  }