i >= 2时
f[i][d]:
状态表示:以第i个位置为结尾,和前一棵树的距离为d(可以没有前一棵树)的所有合法方案集合。
属性:合法的最长数量
状态计算:
f[i][d] = 1; // 初始化
f[i][d] = max(f[i][d], f[j][d] + 1); // i - j = d && h[i] >= h[j]
i = 1时不需要砍树,特判掉即可。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int f[N][N];
int h[N];
int main()
{
while(cin >> n)
{
for(int i = 1;i <= n;i ++ ) cin >> h[i];
memset(f, 0, sizeof f);
if(n == 1)
{
cout << 0 << endl;
continue;
}
for(int i = 1;i <= n;i ++ )
for(int j = 1;j < n;j ++ )
f[i][j] = 1;
for(int i = 1;i <= n;i ++ )
{
for(int j = 1;j < i;j ++ )
{
if(h[i] >= h[j])
{
f[i][i - j] = max(f[i][i - j], f[j][i - j] + 1);
}
}
}
int res = 0;
for(int i = 1;i <= n;i ++ )
for(int j = 1;j < n;j ++ )
res = max(res, f[i][j]);
cout << n - res << endl;
}
return 0;
}