[CF 508E] Arthur and Brackets

這題我是寫DP解，聽說有O(n) 的greedy解，不過我還沒看@@ 感覺好神......

記 dp[ i ][ j ] 是代表第 i 個到第 j 個括號能不能組出一個合法的序列，如果不行就設 -1 ，可以的話就設第 i 個括號的右括號離左括號的距離，狀態有 O(n^2) 個，轉移 O(n)。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=600+10 ;
 
int dp[maxn][maxn],l[maxn],r[maxn] ;
 
void print(int L,int R)
{
    if(L==R) { printf("()") ; return ; }
    if(L>R) return ;
    printf("(") ;
    print(L+1,L+(dp[L][R]-1)/2) ;
    printf(")") ;
    print(L+(dp[L][R]+1)/2,R) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]) ;
    memset(dp,-1,sizeof(dp)) ;
    for(int i=n;i>=1;i--) for(int j=i;j<=n;j++)
    {
        if(i==j)
        {
            if(l[i]==1) dp[i][j]=1 ;
            continue ;
        }
        if(l[i]==1 && dp[i+1][j]!=-1) { dp[i][j]=1 ; continue ; }
        if(2*(j-i)+1>=l[i] && 2*(j-i)+1<=r[i] && dp[i+1][j]!=-1)
            { dp[i][j]=2*(j-i)+1 ; continue ; }
        for(int x=max(1,l[i]/2);j-i>x && 2*x+1<=r[i];x++)
            if(dp[i+1][i+x]!=-1 && dp[i+x+1][j]!=-1)
                { dp[i][j]=2*x+1 ; break ; }
    }
    if(dp[1][n]==-1) printf("IMPOSSIBLE") ;
    else print(1,n) ;
    printf("\n") ;
}