lightoj 1283

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1283

题解：这题很显然一看就像是区间dp，但是单纯的区间dp好像解决不了问题可以稍微利用一下区间dp的思想。其实这题就是单纯的往左右放那么很容易会想到用记忆化搜索。设dp[now][l][r]，now表示处理到哪一位，l表示左边数最靠右的数是哪个。r表示右边最靠左的数是哪个。那么就是简单的记忆化搜索一下就行了。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int a[123] , n;
int dp[123][123][123];
int dfs(int now , int l , int r) {
    if(now > n) return 0;
    if(dp[now][l][r] != - 1) return dp[now][l][r];
    int ans = dfs(now + 1 , l , r);
    if(a[now] >= a[l] && a[now] <= a[r]) {
        ans = max(ans , max(dfs(now + 1 , now , r) + 1 , dfs(now + 1 , l , now) + 1));
    }
    dp[now][l][r] = ans;
    return ans;
}
int main() {
    int t;
    int Case = 0;
    scanf("%d" , &t);
    while(t--) {
        scanf("%d" , &n);
        memset(dp , -1 , sizeof(dp));
        for(int i = 1 ; i <= n ; i++) {
            scanf("%d" , &a[i]);
        }
        a[0] = 0;
        a[n + 1] = 123456;
        printf("Case %d: %d
" , ++Case , dfs(1 , 0 , n + 1));
    }
    return 0;
}