최 장 연속 증가 공공 서브 시퀀스 구하 기

1413 단어 문자열
제목:http://acm.hdu.edu.cn/showproblem.php?pid=5904
제목:최 장 연속 증가 공공 서브 시퀀스
문제 풀이:각 문자 배열 을 이용 하여 dp 를 진행 합 니 다.복잡 도 는 o(n)이 고 모든 숫자 v 에 대해 dp[v]=dp[v-1]+1 을 진행 합 니 다.기억 화 저장 을 했 기 때문에 dp[v]의 숫자 는 증가 하고 감소 하지 않 을 뿐 가장 긴 연속 숫자 길 이 를 확보 합 니 다.그리고 dpa 와 dpb 가 같은 숫자 에서 최소 길이 중의 최대 길 이 를 취하 고 구체 적 으로 다음 과 같 습 니 다.
코드:
#include
#include
#include
#include
#include
#include
#define N 100050

using namespace std;
int v_a[N]; //         
int v_b[N];
int dp_a[N*10];
int dp_b[N*10];
int main()
{
    int t;
    memset(dp_a,0,sizeof(dp_a));
    memset(dp_b,0,sizeof(dp_b));
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&v_a[i]);
            dp_a[v_a[i]]=dp_a[v_a[i]-1]+1;
        }
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&v_b[j]);
            dp_b[v_b[j]]=dp_b[v_b[j]-1]+1;
        }
        int maxx=0;
        for(int i=1;i<=n;i++)
        {
            maxx=max(maxx,min(dp_a[v_a[i]],dp_b[v_a[i]]));
            dp_a[v_a[i]]=0;
        }
        for(int i=1;i<=m;i++)
        {
            dp_b[v_b[i]]=0;
        }
        printf("%d
",maxx); } return 0; }

좋은 웹페이지 즐겨찾기