考慮狀态的dp(最長單調遞增子序列）

題目：

題解：

以​

​ababc​

​為例:

j/i/dp[i]	a	b	a	b	c
a	1
b	1	2
a	1	2	1
b	1	2	1	2
c	1	2	1	2	3

這就是這個表格的圖，因為某個點都可能為起點，是以每個點的最開始的狀态為1，以這個點往後更新

if(s[i]>s[j])
{
  dp[i]=max(dp[i],dp[j]+1);
  就應該保持這個狀态，dp[j]是
  以某個點為起點的最大公共遞增子序列,由于dp[i]>dp[j],呢麼
  目前最優解:max(dp[j]+1,dp[i])
  }      

#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
int dp[maxn];
char s[maxn];
void dp_max()
{
    memset(dp,0,sizeof(dp));
    memset(s,0,sizeof(s));
    scanf("%s",s+1);
    int len=strlen(s+1);
    char str;

    for(int i=1; i<=len; i++)
    {
        dp[i]=1;
        for(int j=1; j<i; j++)
        {
            if(s[i]>s[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }

        }
    }


 printf("%d\n",dp[len]);

}
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        dp_max();
    }


}      

#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
char Stack[maxn];//最長遞增子序列
char s[maxn];
int lower_ans(int l,int r,int i)//二分答案
{
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(s[i]>Stack[mid])
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    return l;
}
void slove_dp()
{
    int len=strlen(s);
    int top=1;
    Stack[top]=s[0];
    for(int i=1;i<len;i++)
    {
        if(s[i]>Stack[top])
        {
            Stack[++top]=s[i];//入棧
        }
        else
        {
            Stack[lower_ans(1,top,i)]=s[i];//替位
        }
    }
    printf("%d\n",top);
}
int main()
{

    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(s,0,sizeof(s));
        memset(Stack,0,sizeof(Stack));
        scanf("%s",s);
        slove_dp();
    }
}