Loading...

洛谷P1799 数列_NOI导刊2010提高(06)

check评论:0 条 remove_red_eye浏览量:425 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-18

我居然做出了一道绿色的$dp$题目$\text{qwq}$

好激动$\text{qwq}$

我们很容易的想到设$dp[i][j]$表示前$i$个数里删除了$j$个的最大值$(j \leq i)$

则当$j \leq i+1$时,$dp[i][j]=max(dp[i][j],dp[i-1][j]+(a[i]==(i-j)))\text{(当前这个数不删)}$

其余时候$dp[i][j]=max(dp[i][j],dp[i-1][j-1])\text{这个数也要删}$

然后跑一遍就行,时间复杂度$O(n^2)$

上代码:

#include <bits/stdc++.h>
using namespace std;
int dp[1010][1010];//前i个数擦了j个 
int a[1010];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j<i)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j]+(a[i]==(i-j)));
            }
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
        }
    }
    int ans=-1;
    for(int i=0;i<=n;i++)
    {
        ans=max(ans,dp[n][i]);
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名