战斗机的祈雨仪式（NOIP模拟赛Round 7）

【问题描述】

炎炎夏日，如果没有一场大雨怎么才能尽兴？秋之国的人民准备了一场祈雨仪式。战斗机由于拥有操纵雷电的能力，所以也加入了其中，为此，她进行了一番准备。

战斗机需要给自己的Spear of Longinus灌注法力。Longinus的长度为n，战斗机为它制作了一个长度相等的灌注槽，因此这个灌注槽就被等分为了n段，每一段有两个增益值ai、bi。战斗机可以对每一段指定一个灌注的法力类型，每一段都有两种类型（A、B）可选，战斗机需要在灌注法力前确定好这n段所灌注的法力类型。由于仪式的需要，其中有m1段要强制选择A类法力，m2段要强制选择B类法力。

确定完每段所灌注的法力类型时，接下来就是法力灌注的过程。n段灌注槽中分别灌满了代表该段所选定法力类型的结晶，且一开始每段的法术强度都为0。每次战斗机需要合并相邻的两段成为新的一段，新的一段结晶的法术强度除了包括两段结晶的法术强度总和以外，还两段结晶两端处的结晶的法力类型有关，如果两段结晶左（右）端的法力类型相异，那么合并后的结晶的法术强度还要加上两段结晶左（右）端的a增益值之积；如果两段结晶左（右）端的法力类型相同，那么合并后的结晶的法术强度还要加上两段结晶左（右）端的b增益值之积。举个例子：

灌注槽的长度为n，所以一开始有n段结晶。战斗机要把它们合并成一整段结晶为Longinus灌注法术，她希望为祈雨仪式增光添彩，所以她希望找到一个灌注法力和合并结晶的方案，使Spear of Longinus被灌注的法术强度尽可能大。

【数据范围】

对于10%的数据，n<=10；

对于50%的数据，m1,m2<=5；

对于另外20%的数据，m1+m2=n；

对于100%的数据，0<=m1,m2<=200，0<αi,βi<=n<=200，

0<αi,βi<=1000，保证ai,bi各不相同。

————————————————我是分割线————————————————

这道题目就是不断合并区间，取最大值并记录答案。并且有一些点我们可以随意取蓝或红。

这当然就是一道区间DP题，并且我们所得到的强制要取的m1+m2段就是将一些DP状态删除(设为-INF)

然后只要列出DP方程就好啦！

虽然这道题有7个for循环，但是不用担心，我们有注释QAQ

下面贴代码

#include <cstdio>

#include <algorithm>

#define MN 205

#define INF 0x2FFFFFFF

using namespace std;

int n,m1,m2,ans,bj[MN],a[][MN],f[MN][MN][][];

inline int read()

{

    int n=,f=; char c=getchar();

    while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}

    while (c>='' && c<='') {n=n*+c-''; c=getchar();}

    return n*f;

}

int main()

{

//    freopen("lightning.in","r",stdin);

//    freopen("lightning.out","w",stdout);

    register int i,j,jl,jr,k,g1,g2,g3,g4;

    n=read(); m1=read(); m2=read();

    for (i=;i<=n;++i) bj[i]=;//初始化

    while (m1--) bj[read()]=;//

    while (m2--) bj[read()]=;//

    for (i=;i<=n;++i) a[][i]=read(),a[][i]=read();//a,b两种增益

    for (i=;i<=n;++i) f[i][i][][]=f[i][i][][]=-INF;//因为当只有一个点的时候不可能左边和右边不同

    for (i=;i<=n;++i)

        for (j=i;j<=n;++j)

        {

            if (bj[i]<) f[i][j][bj[i]^][]=f[i][j][bj[i]^][]=-INF;//同上

            if (bj[j]<) f[i][j][][bj[j]^]=f[i][j][][bj[j]^]=-INF;

        }

    for (i=;i<n;++i)//枚举长度

        for (jl=,jr=i+;jr<=n;++jl,++jr)//枚举相同长度的区间

            for (g1=;g1<;++g1)//

                for (g2=;g2<;++g2)//枚举区间2段的选取情况

                    if (f[jl][jr][g1][g2]!=-INF)

        for (k=jl;k<jr;++k)//枚举断点

            for (g3=;g3<;++g3)//枚举断点两端的选取情况

                for (g4=;g4<;++g4)

                    f[jl][jr][g1][g2]=max(f[jl][jr][g1][g2],f[jl][k][g1][g3]+f[k+][jr][g4][g2]+a[g1^g4][jl]*a[g1^g4][k+]+a[g2^g3][jr]*a[g2^g3][k]);

    for (g1=;g1<;++g1)

        for (g2=;g2<;++g2) if (f[][n][g1][g2]!=-INF) ans=max(ans,f[][n][g1][g2]);

    printf("%d",ans);

}