最少砍掉的树-解题报告

题目

题目描述

　　时间限制：1000ms
　　内存限制：256MB
　　多组测试用例，每组测试用例给出不超出1000棵树，并且第二行给出每棵树的高度，初始时，相邻两个树的距离都相等，需要砍掉最少的树是的这些树高度呈现非递减的序列并且相邻之间距离要相等，输出最少砍的树的数组。

输入描述

　　输入树的棵树n，然后接下来一行输入n个正整数表示树的高度，整数之间以空格为隔。

输出描述

　　最少砍掉的树的棵树。

样例

　　input

6
6 5 4 3 2 1
10
1 9 2 8 3 2 4 6 5 2
5
1 2 6 2 4

　　output

5
5
2

解题

思路

　　根据题目描述，我们可以将题目转换为”求解最长等间隔连续非递减序列长度问题“，然后很容易得到总的树木棵数-符合条件的最长序列长度=需要砍掉的树木棵数。显然，对于这类问题我们可以采用动态规划的思想来做。
　　第一步：确定动态规划dp数组的含义：dp[i][j]表示i下标（包含i）之前的间隔为j的连续非递减序列的长度。
　　第二步：确定边界条件：对于数组中的每一个元素而言，有两种情况：①自己是当前间隔长度的第一个元素；②与当前间隔的前一个元素不构成非递减序列。以上两种情况下，dp数组的值为1，表示序列中只有自己。
　　第三步：确定状态转移方程：如果以当前间隔计算，能和前一个元素构成非递减序列，那么当前dp值等于前一个位置的dp值+1，即dp[i][j]=dp[i-j][j]+1;。
　　最后，我们在更新dp数组的时候记录符合要求的最长序列长度即可。
　　解题代码如下所示：

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        vector<int> data(n);
        //dp含义：dp[i][j]表示i下标（包含i）之前的间隔为j的连续非递减序列的长度
        //边界条件为仅包含自身，因此初始化长度为1（包含自己是当前间隔长度的第一个，或者与前一个等间隔元素不构成非递减序列两种情况）
        //间隔长度为0,1,2,3,...,n
        vector<vector<int>> dp(n,vector<int>(n+1,1)); 
        //入读一组数据
        for(int i=0;i<n;i++){
            cin>>data[i];
        }
        //初始化长度为1
        int maxValue = 1;
        for(int i=1;i<n;i++){
            for(int j=1;j<=n;j++){
                if(i-j<0) break;            //如果j长度间隔之前没有元素了，那么更长的长度也不可能有前驱元素，所以直接跳出
                if(data[i]>=data[i-j]){     //如果j长度之前有元素，而且能够构成非递减序列，那么状态转移
                    dp[i][j]=dp[i-j][j]+1;  //长度+1
                    maxValue =max(maxValue,dp[i][j]);  //更新最长的序列长度值
                }
            }
        }
        cout<<n-maxValue<<endl;             //需要砍掉的数量为总数减去符合条件的最长序列
    }
    return 0;
}