[線形ダイナミックプランニング][最長上昇/下降シーケンス][P 1001合唱隊形]線形ダイナミックプランニング問題の理解と総括
P 1091合唱隊形
問題を解く構想.
まずテーマの説明から分かるように、最も長い共通のサブシーケンスを求める問題は明らかで、i番目の同級生の左側に対して最も長い上昇サブシーケンスを求め、右側に対して最も長い上昇サブシーケンスを求め、動的計画思想を利用して、最後に両者を加えて最大のi番目のビットを求める.最終的に答えを求める.
コード:
問題を解く構想.
まずテーマの説明から分かるように、最も長い共通のサブシーケンスを求める問題は明らかで、i番目の同級生の左側に対して最も長い上昇サブシーケンスを求め、右側に対して最も長い上昇サブシーケンスを求め、動的計画思想を利用して、最後に両者を加えて最大のi番目のビットを求める.最終的に答えを求める.
コード:
#include
#include
using namespace std;
int Height[101];
int N;
//0: ;
//1: ;
int DP[101][2];
int main(void)
{
cin >> N;
for(int i = 1;i <= N;i++)
{
cin >> Height[i];
}
/* i */
for(int i = 1;i <= N;i++)
{
DP[i][0] = 1;
for(int j = 1;j < i;j++)
{
if(Height[j] < Height[i])
{
DP[i][0] = max(DP[i][0],DP[j][0]+1);
}
}
}
/* i */
for(int i = N;i >= 1;i--)
{
DP[i][1] = 1;
for(int j = N;j > i;j--)
{
if(Height[j] < Height[i])
{
DP[i][1] = max(DP[i][1],DP[j][1]+1);
}
}
}
int ans = 0;
for(int i = 1;i <= N;i++)
{
/* i */
ans = max(DP[i][1]+DP[i][0]-1,ans);
}
cout << N-ans << endl;
return 0;
}