合唱隊(duì)形

jzoj 1122

題目大意：

有n個(gè)人，按一定的順序站成一排，最少減去多少個(gè)人可以使隊(duì)列以一個(gè)人為中心，兩邊分別遞減

輸入樣例

8 186 186 150 200 160 130 197 220

輸出樣例

4

數(shù)據(jù)范圍

對(duì)于50％的數(shù)據(jù)，保證有n<=20；
對(duì)于全部的數(shù)據(jù)，保證有n<=100。

解題思路：

分別正著和逆著跑一遍最長(zhǎng)上升子序列，然后找一個(gè)最優(yōu)點(diǎn)加在一起即可

代碼：

#include<cstdio> #define max(x,y) (x)>(y)?(x):(y) using namespace std; int n,ans,a[150],l[150],r[150]; int main() {scanf("%d",&n);for (int i=1;i<=n;++i){scanf("%d",&a[i]);l[i]=1;for (int j=1;j<i;++j)//正著if (a[j]<a[i])l[i]=max(l[i],l[j]+1);}for (int i=n;i>0;--i){r[i]=1;for (int j=n;j>i;--j)//倒著if (a[j]<a[i])r[i]=max(r[i],r[j]+1);}for (int i=1;i<=n;++i)//找一個(gè)中點(diǎn)ans=max(ans,l[i]+r[i]-1);printf("%d",n-ans); }

總結(jié)

以上是生活随笔為你收集整理的【DP】合唱队形（jzoj 1122）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。