题目链接
简单DP
- 更改某一列等价于删除这一列
- 只有斜率>0的柱形会增加笔画数，可用
评价价值（value）
dp[i][j] := 第i列不删、第i列和之前总和j列、第i列之后全删的最小笔画数（value最小）
初始化：
状态转移等式：
坑点1
特判：N==K
#include<bits/stdc++.h>
using namespace std;
//省略一些宏
//---------------------
#define MAXN 305
#define INF (INF_LL >> 10ll)
//---------------------
ll n,k;
ll h[MAXN];
ll dp[MAXN][MAXN];
int main(){
cin >> n >> k;
REP1(i,n) cin >> h[i];
h[0] = 0;
REP(i,MAXN) REP(j,MAXN) dp[i][j] = INF;
dp[0][0] = 0;
REP1(i,n) REP1(j,i) REP(m,i){
DBPRT(m);
DBPRT((j-1));
dp[i][j] = min(dp[i][j],dp[m][j-1]+max(0ll,h[i]-h[m]));
}
DBSTART
PRTLST2(dp,n+1,n-k+1);
DBEND
ll res = INF;
REP(i,n+1) res = min(res,dp[i][n-k]);
PRT(res);
return 0;
}
