拦截导弹（NYOJ—79）最长字串问题（NYOJ

拦截导弹（NYOJ—79）最长字串问题（NYOJ—17）

这是到动态规划的题目，属于有顺序的0 1 背包问题；

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 int d[20][100000];  //d[i][j]
 5 int a[20];
 6 int N;
 7 
 8 int max(int a, int b)
 9 {
10     return a>b?a:b;
11 }
12 
13 int solve(int i,int high)
14 {
15     if(d[i][high]>=0)
16         return d[i][high];
17     if(i==N)
18     {
19         if(a[i]<high)
20             return d[N][high]=1;
21         else
22             return d[N][high]=0;
23     }
24     if(a[i]<high)
25         return d[i][high]=max(solve(i+1,a[i])+1,solve(i+1,high));          //打击和不打击  取大者
26     else
27         return d[i][high]=solve(i+1,high);
28 }
29 
30 int main()
31 {
32     int T;
33     scanf("%d",&T);
34     while(T--)
35     {
36         memset(d,-1,sizeof(d));
37         scanf("%d",&N);
38         for(int i=1; i<=N; i++)
39         {
40             scanf("%d",&a[i]);
41         }
42         printf("%d
",solve(0,9999));
43     }
44     return 0;
45 }

但这个代码提交会得到RE，至于为什么可能是记忆话搜索对这个的复杂度减小的比较小，所以递归深度太深，造成堆栈溢出。

我想多了，不是这个原因，是我没有注意到下标越界了。

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 int d[22][1000];  //d[i][j]
 5 int a[22];
 6 int N;
 7 
 8 int max(int a, int b)
 9 {
10     return a>b?a:b;
11 }
12 
13 int solve(int i,int high)
14 {
15     if(d[i][high]>=0)
16         return d[i][high];
17     if(i==N)
18     {
19         if(a[i]<high)
20             return d[N][high]=1;
21         else
22             return d[N][high]=0;
23     }
24     if(a[i]<high)
25         return d[i][high]=max(solve(i+1,a[i])+1,solve(i+1,high));          //打击和不打击  取大者
26     else
27         return d[i][high]=solve(i+1,high);
28 }
29 
30 int main()
31 {
32     int T;
33     scanf("%d",&T);
34     while(T--)
35     {
36         memset(d,-1,sizeof(d));
37         scanf("%d",&N);
38         for(int i=1; i<=N; i++)
39         {
40             scanf("%d",&a[i]);
41         }
42         printf("%d
",solve(1,999));
43     }
44     return 0;
45 }

我不知道原来这种问题叫最长递增子序列问题我还给他起了个（顺序0 1 背包问题），我这就透过本质起的名字。

最长字串问题（NYOJ - 17）

AC代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int d[10002][180];
char a[10002];
int N;

int max(int a, int b)
{
    return a>b?a:b;
}

int dp(int i, char c)
{
    if(d[i][c]>=0)
        return d[i][c];
    if(i==N-1)
    {
        if(a[i]>c)
            return d[i][c] = 1;
        else
            return d[i][c] = 0;
    }
    if(a[i]>c)
        return d[i][c]=max(dp(i+1,c),dp(i+1,a[i])+1);
    else
        return d[i][c]=dp(i+1,c);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(d,-1,sizeof(d));
        scanf("%s",a);
        N = strlen(a);
        printf("%d
",dp(0,0));
    }
    return 0;
}

View Code

拦截导弹 （NYOJ—79） 最长字串问题 （NYOJ—17）

拦截导弹（NYOJ—79）最长字串问题（NYOJ—17）