公司建设一个网站,网站空间是指什么,wordpress 漏洞工具,怎样申请小程序前言
我切掉这道题是命运石之门的选择 正题
题目链接:https://www.luogu.org/problemnew/show/P2101 题目大意 nnn个连在一起的高度hih_ihi盒子。一个刷子只能直着刷而且得连续都得刷。求至少刷多少次。 解题思路 fi,jf_{i,j}fi,j表示前iii个已经刷完了#xff0c;上一个…前言
我切掉这道题是命运石之门的选择 正题
题目链接:https://www.luogu.org/problemnew/show/P2101 题目大意
nnn个连在一起的高度hih_ihi盒子。一个刷子只能直着刷而且得连续都得刷。求至少刷多少次。 解题思路
fi,jf_{i,j}fi,j表示前iii个已经刷完了上一个高度为jjj的刷过来。首先我们要把jjj离散化了。 然后考虑fi,jmin{fi−1,k(k≥j),fi,j−1bi−bj}f_{i,j}min\{f_{i-1,k(k\geq j)},f_{i,j-1}b_i-b_j\}fi,jmin{fi−1,k(k≥j),fi,j−1bi−bj} 这样横着刷的就搞定了但是还有竖着刷的所以就要加(b[j]!a[i])(b[j]!a[i])(b[j]!a[i]) 然后对于那个kkk用前缀合搞定。 codecodecode
#includecstdio
#includealgorithm
#includecstring
#define ll long long
using namespace std;
const ll N5100;
ll n,a[N],b[N],f[2][N],mins,m;
int main()
{scanf(%lld,n);for(ll i1;in;i){scanf(%lld,a[i]);b[i]a[i];}sort(b1,b1n);munique(b1,bn1)-(b1);memset(f,0x3f,sizeof(f));f[0][0]0;mins2147483647;for(ll i1;in;i){memset(f[i1],0x3f,sizeof(f[i1]));f[i1][0]f[~i1][0];for(ll j1;jm;j){if(b[j]a[i]) break;f[i1][j]min(f[~i1][j],f[i1][j-1]b[j]-b[j-1]);}for(ll j0;jm;j){if(b[j]a[i]) break;if(b[j]!a[i]) f[i1][j]1;if(in) minsmin(f[i1][j],mins);}for(ll jm-1;j0;j--)f[i1][j]min(f[i1][j1],f[i1][j]);}printf(%lld,mins);
}
