2016 UESTC Training for Dynamic Programming

强行做做试试看吧。

http://acm.hust.edu.cn/vjudge/contest/124721#overview

密码:mytrain

C - 柱爷与咸鱼神功

一个简单01背包。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
#define maxn 1000005
const int inf=0x3f3f3f3f;
const LL mod=;
int v[];
int t[];
int p[];
int main()
{
#ifdef local
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int _time=clock();
#endif
    int n,m;
    cin>>m>>n;
    for(int i=;i<n;i++)
    {
        scanf("%d%d",&t[i],&p[i]);
    }
    for(int i=;i<n;i++)
    {
        for(int j=m;j>=t[i];j--)
        {
            v[j]=max(v[j],v[j-t[i]]+p[i]);
        }
    }
    cout<<v[m]<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

E - 柱爷与最大区间和

题意从一个区间中选取两个不相邻的区间使得这两个区间和最大.

dp[i][j]表示前j个数分成i份时且选择最后一个数的最大和，dp[i][j]=max(dp[i][j-1]+num[j],dp[i-1][k]+num[j]) (0<k<j-1)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
#define maxn 1000005
const int inf=0x3f3f3f3f;
const LL mod=;
int dp[][];
int pre[];
int num[];
int main()
{
#ifdef local
    freopen("in","r",stdin);
   // freopen("out","w",stdout);
    int _time=clock();
#endif
    int n;
    cin>>n;
    for(int i=;i<=n;i++)
    {
        sd(num[i]);
        pre[i-]=-inf;
    }
    dp[][]=-inf;
    for(int i=;i<=n;i++)
    {
        dp[][i]=max(dp[][i-]+num[i],num[i]);
    }
    pre[]=dp[][];
    for(int i=;i<=n;i++)
    {
        pre[i]=max(pre[i-],dp[][i]);
    }
    dp[][]=-inf;
    for(int j=;j<=n;j++)
    {
        dp[][j]=max(dp[][j-],pre[j-])+num[j];
    }
    int ans=-inf;
    for(int i=;i<=n;i++)
    ans=max(dp[][i],ans);
    cout<<ans<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

Q - 柱爷的下凡

01背包，打表预处理一下，肯定第一个硬币是1的，枚举另两个

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
#define maxn 1000005
const int inf=0x3f3f3f3f;
const LL mod=;
int ans1[],ans2[];
void init()
{
    ans1[]=,ans2[]=;
    ans1[]=,ans2[]=;
    ans1[]=,ans2[]=;
    ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
ans1[]=,ans2[]=;
}
/*
int num[4]={0,1};
int dp[205];
void biao()
{
    for(int n=4;n<=200;n++)
    {
        int b,c;
        int cnt=inf;
        for(num[2]=2;num[2]<n;num[2]++)
        {
            for(num[3]=num[2]+1;num[3]<=n;num[3]++)
            {
                memset(dp,127/3,sizeof dp);
                dp[0]=0;
                for(int i=1;i<=3;i++)
                {
                    for(int j=num[i];j<=n;j++)
                    {
                        dp[j]=min(dp[j-num[i]]+1,dp[j]);
                    }
                }
                for(int i=1;i<=n;i++)
                    dp[i]+=dp[i-1];
                if(dp[n]<cnt)
                {
                    b=num[2],c=num[3];
                    cnt=dp[n];
                }
            }
        }
        printf("ans1[%d]=%d,ans2[%d]=%d;\n",n,b,n,c);
    }
}*/
int main()
{
#ifdef local
    freopen("in","r",stdin);
  //  freopen("out","w",stdout);
    int _time=clock();
#endif
   // biao();
   init();
   int T;
   cin>>T;
   while(T--)
   {
       int n;
       cin>>n;
       printf("%d %d %d\n",,ans1[n],ans2[n]);
   }
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

B - 柱爷大战滑稽王

求LCS，但是数据n是1e6,特殊的是Ai每个数都不同，我们可以把LCS转LIS，记录Ai在Bi的位置作为一个序列，然后求出这个序列的LIS就是LCS了，这个网上有挺多的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
#define maxn 1000005
const int inf=0x3f3f3f3f;
const LL mod=;
map<int,int>mp;
int x[];
int d[];
int lis(int n)
{
    if(!n)return ;
    int ans=;
    d[]=x[];
    for(int i=;i<n;i++){
        if(x[i]>d[ans])d[++ans]=x[i];
        else{
            int pos=lower_bound(d,d+ans+,x[i])-d;
            d[pos]=x[i];
        }
    }
    return ans+;
}
int main()
{
#ifdef local
    freopen("in","r",stdin);
  //freopen("out","w",stdout);
    int _time=clock();
#endif
    int n,m,c;
    int a;
    mp.clear();
    cin>>n>>m;
    for(int i=;i<=n;i++){
        sd(a);
        mp[a]=i;
    }
    n=;
    for(int i=;i<m;i++){
        sd(a);
        c=mp[a];
        if(c){
            x[n++]=c;
        }
    }
    cout<<lis(n)+<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

N - 柱爷抢银行II

一个环，在环中连续取至多k个数，使得取的数和最大

记sum[i]为前i项和，dp[i]为以i结尾时，dp[i]-i这段范围取得和最大，所以dp[i]=x(i-k<x<i,且max(sum[i]-sum[x])).

单调队列维护sum[i]递减就行

代码写的很渣。。感觉这题有点奇怪题目说了如果想等的话就选区间最小的

3 2

0 0 3

。这种数据，我开始的代码是显示3 3 3一直wa，改了单调队列一点之后变成3 2 3然后居然AC了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
#define maxn 1000005
const int inf=0x3f3f3f3f;
const LL mod=;
LL sum[];
LL dp[];
LL x[];
int q[];
int main()
{
#ifdef local
    freopen("in","r",stdin);
  //freopen("out","w",stdout);
    int _time=clock();
#endif
    LL c;
    int l,r;
    int n,k;
    cin>>n>>k;
    for(int i=;i<=n;i++){
        cin>>x[i];
        sum[i]=sum[i-]+x[i];
    }
    for(int i=n+;i<=*n;i++){
        sum[i]=sum[i-]+x[i-n];
    }
    q[]=;
    int head=,tail=;
    for(int i=;i<=*n;i++)
    {
        while(head<=tail&&i-q[head]>k)head++;
        dp[i]=q[head];
        while(sum[i]<sum[q[tail]]&&tail>=head)tail--;
        q[++tail]=i;
    }
    int t=;
    for(int i=;i<=*n;i++)
    {
        if(sum[i]-sum[dp[i]]>sum[t]-sum[dp[t]])
        {
            t=i;
        }
        else if(sum[i]-sum[dp[i]]==sum[t]-sum[dp[t]]&&(i-dp[i]<t-dp[t]||(dp[t]+)-((dp[t]+)>n?n:)>(dp[i]+)-((dp[i]+)>n?n:)))
        {
            t=i;
        }
    }
    c=sum[t]-sum[dp[t]];
    r=t-(t>n?n:);
    l=(dp[t]+)-((dp[t]+)>n?n:);
    cout<<c;
    printf(" %d %d\n",l,r);
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

L - 柱爷的矩阵

假如要选i,j,如果b[i]>b[j],那我们肯定先选b[i],所以先按b[i]降序排序

dp[i][j]表示选取第i列第j行时的最大值,

dp[i][j]=max(dp[i-1][k])(k<j)+max(a[j]-b[j]*(i-1),0);

dp[i-1][k]这个东西我们可以用多个二维数组来维护pre[i][j]=max(dp[i][j-1],dp[i][j]);

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
#define maxn 1000005
const int inf=0x3f3f3f3f;
const LL mod=;
struct node
{
    int a,b;
}mp[];
bool cmp(node a,node b)
{
    return a.b>b.b;
}
int dp[][];
int p[][];
int main()
{
#ifdef local
    freopen("in","r",stdin);
  //freopen("out","w",stdout);
    int _time=clock();
#endif
    int n,m;
    cin>>n>>m;
    for(int i=;i<n;i++)
    {
        cin>>mp[i].a;
    }
    for(int i=;i<n;i++)
    {
        cin>>mp[i].b;
    }
    sort(mp,mp+n,cmp);
    int ans=;
    for(int i=;i<=m;i++)
    {
        for(int j=;j<n;j++)
        {
            dp[i][j]=p[i-][j-]+max(mp[j].a-mp[j].b*(i-),);
            p[i][j]=max(p[i][j-],dp[i][j]);
            ans=max(p[i][j],ans);
        }
    }
    cout<<ans<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

I - 柱爷与子序列

这题和FZU有一题很像。树状数组好题。

dp[i]=sum(dp[A[i]]-k],dp[A[i]]+k])+1.

这样答案算是算不考虑m>=2的。所以我们最后需要减去n;

每次查询(A[i]-k，A[i]+k)区间和=sum，然后再在add(A[i],sum+1),最后read(最远点)-n.数据太大，需要离散化一下。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
#define maxn 1000005
const int inf=0x3f3f3f3f;
const int mod=;
int nn;
int tree[];
int a[],b[];
void add(int d,int x)
{
    while(d<=nn)
    {
        tree[d]=(tree[d]+x)%mod;
        d+=(d&-d);
    }
}
int read(int x)
{
    int sum=;
    while(x)
    {
        sum=(sum+tree[x])%mod;
        x-=(x&-x);
    }
    return sum;
}
int main()
{
#ifdef local
    freopen("in","r",stdin);
  //freopen("out","w",stdout);
    int _time=clock();
#endif
    int n,k;
    cin>>n>>k;
    for(int i=;i<n;i++)
    {
        sd(a[i]);
        b[i]=a[i];
    }
    sort(a,a+n);
    nn=unique(a,a+n)-a;
    int z,l,r;
    for(int i=;i<n;i++)
    {
        z=lower_bound(a,a+nn,b[i])-a+;
        l=lower_bound(a,a+nn,b[i]-k)-a+;
        r=upper_bound(a,a+nn,b[i]+k)-a;
        int sum=(read(r)-read(l-)+mod)%mod;
        add(z,sum+);
    }
    cout<<(read(nn)-n+mod)%mod<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

G - 柱爷与三叉戟不得不说的故事

15种元素，状压DP搞一下1<<15种状态，

dp[i]=min(dp[i],dp[j]+dp[i^j]);

开始全部初始化为最大值，然后根据条件保留各个状态的最小值最后答案是dp[1<<15-1];

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
const int inf=0x3f3f3f3f;
const int mod=;
const int maxn=(<<)+;
int dp[maxn];
int main()
{
#ifdef local
    freopen("in","r",stdin);
  //freopen("out","w",stdout);
    int _time=clock();
#endif
    memset(dp,/,sizeof dp);
    int d,a;
    for(int i=;i<;i++)
        cin>>d,dp[<<i]=d;
    int n;
    cin>>n;
    for(int i=;i<n;i++)
    {
        int m;
        sd(m);
        int sta=;
        for(int j=;j<m;j++)
        {
            sd(a);
            sta+=(<<(a-));
        }
        cin>>d;
        dp[sta]=min(dp[sta],d);
    }
    int last=(<<)-;
    for(int i=;i<=last;i++)
    {
        for(int j=i;j;j=(j-)&i)
        {
            dp[i]=min(dp[i],dp[j]+dp[j^i]);
        }
    }
    cout<<dp[last]<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

A - 柱爷的恋爱

区间dp

dp[i][j]表示[i,j)的所有合法方案

dp[i][i]=1;

然后我们记忆化递归

dfs(i,j)

假设我们不删i的话我们就需要找出和i对应的括号来算

res+=dfs(i+1,a)*dfs(a+1,j);算出每一个a.

如果删去i就是直接res+=dfs(i+1,j);

最后减1，因为答案不允许删掉所有东西。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
const int inf=0x3f3f3f3f;
const int mod=;
const int maxn=+;
LL dp[maxn][maxn];
char s[maxn];
LL dfs(int l,int r)
{
    int ans=;
    if(dp[l][r]!=-)return dp[l][r];
    if(l==r)
        ans=;
    else
    {
        dp[l][r]=;
        char fi='\0';
        if(s[l]=='(')fi=')';
        if(s[l]=='[')fi=']';
        if(fi!='\0')
        {
            for(int i=l+; i<r; i++)
            {
                if(s[i]==fi)
                {
                    ans=(ans+dfs(l+,i)*dfs(i+,r))%mod;
                }
            }
        }
        ans=(ans+dfs(l+,r))%mod;
    }
    dp[l][r]=ans;
    return ans;
}
int main()
{
#ifdef local
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int _time=clock();
#endif
    for(int i=; i<maxn; i++)for(int j=; j<maxn; j++)dp[i][j]=-;
    int n;
    cin>>n;
    cin>>s;
    cout<<(dfs(,n)+mod-)%mod<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

M - 柱爷的宝藏

普通转移就是，记dp[i]为以i结尾的最大值

dp[i]=max(dp[j]+(sum[i]-sum[j])^2+m);

n^2肯定TLE。然后就学到一个奇妙的斜率优化。。(http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))//GL&HF
#define ss(x) scanf("%s",(x))
const int inf=0x3f3f3f3f;
const int mod=;
const int maxn=+;
LL dp[];
LL sum[];
LL m;
int q[];
int n;
LL getdp(int i,int j)
{
    return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
}
LL dp_up(int i,int j)
{
    return dp[i]+sum[i]*sum[i]-(dp[j]+sum[j]*sum[j]);
}
LL dp_down(int i,int j)
{
    return 1LL**(sum[i]-sum[j]);
}
int main()
{
#ifdef local
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int _time=clock();
#endif
    cin>>n>>m;
    for(int i=;i<=n;i++)
        cin>>sum[i],sum[i]+=sum[i-];
    dp[]=;
    int head=,tail=;
    q[tail++]=;
    for(int i=;i<=n;i++)
    {
        while(head+<tail&&dp_up(q[head+],q[head])<=sum[i]*dp_down(q[head+],q[head]))head++;
        dp[i]=getdp(i,q[head]);
        while(head+<tail&&dp_up(i,q[tail-])*dp_down(q[tail-],q[tail-])<=dp_up(q[tail-],q[tail-])*dp_down(i,q[tail-]))tail--;
        q[tail++]=i;
    }
    cout<<dp[n]<<endl;
#ifdef local
    printf("time: %d\n",int(clock()-_time));
#endif
}

还有几题有点打算弃坑。。