Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这个想法不错啊,非递归dp,1500+ms

Posted by zhanggt1994 at 2014-03-20 19:58:21 on Problem 3056
In Reply To:【好题】考想法,小dp Posted by:WilliamACM at 2013-04-26 20:57:10
> n为奇数时为0;
> 偶数时:
> 把环打开,1~n,我们要做的,是连不交叉的线,环时不交叉的线,把数字排成一行时也是不交叉的,做dp, dp[i][j],为i到j连完不交叉的线后的最大的答案数(注意保持j-i+1是偶数!!!)。。。。
> dp[i][j]=max(dp[i+1][j-1],dp[i][k]+dp[k+1][j]));大致就是这样的dp,O(n*n)  dp
> 
> 
> 
> #include <iostream>
> #include <stdio.h>
> #include <string.h>
> #include <algorithm>
> using namespace std;
> const int N=1000;
> int dp[N][N];
> int a[N],n;
> int dfs(int s,int t)
> {
>     int &d=dp[s][t];
>     if(~d) return d;
>     if(s==t-1)
>     {
>         return d=(a[s]==a[t]);
>     }
>     d=(a[s]==a[t])+dfs(s+1,t-1);
>     for(int i=s+1;i<t;i+=2) d=max(d,dfs(s,i)+dfs(i+1,t));
>     return d;
> }
> int main()
> {
>    // freopen("in.txt","r",stdin);
>     int w;cin>>w;
>     while(w--)
>     {
>         scanf("%d",&n);
>         for(int i=0;i<n;i++) scanf("%d",a+i);
>         if(n&1)
>         {
>             puts("0");
>             continue;
>         }
>         memset(dp,-1,sizeof(dp));
>         printf("%d\n",dfs(0,n-1));
>     }
> //    cout << "Hello world!" << endl;
>     return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator