DP刷题笔记I

xtx1092515503 · 2020-03-13 08:47:45 · 个人记录

发现自己DP学的很糟糕……难一点的DP根本不会做……因此决定不管三七二十一先刷上百十来道再说……

O.前提

本笔记的重点是状态的设计，在转移简单的时候就会一笔带过。

当然，如果转移也比较恶心，会提到的。

I.[JSOI2010]快递服务

我们约定共有n个地点，依次登记了m家公司。

思路1.

设f[l][i][j][k]表示：当前某一个司机在第i家公司（注意是公司！1000家那个！），第二个司机在第j家，第三个司机在第k家，当前我们遍历到了第l家公司。依次转移即可。

复杂度O(m^4)。

思路2.观察到i,j,k中必有一个等于l（不然你位置l的货是哪辆车发的？），因此我们可以省掉一维。设f[i][j][k]即可。

复杂度O(m^3)。

明显第一维可以滚动掉，因此空间复杂度便可以通过。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,dis[210][210],f[2][1010][1010],pos[1010],m,res=0x3f3f3f3f;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&dis[i][j]);
    memset(f,0x3f3f3f3f,sizeof(f)),f[1][2][1]=0;
    pos[++m]=1,pos[++m]=2,pos[++m]=3;
    while(scanf("%d",&pos[++m])!=EOF);
    for(int i=3;i<m;i++){
        for(int j=1;j<=i;j++)for(int k=1;k<j;k++)f[!(i&1)][j][k]=0x3f3f3f3f;
        for(int j=1;j<i;j++)for(int k=1;k<j;k++){
            f[!(i&1)][j][k]=min(f[!(i&1)][j][k],f[i&1][j][k]+dis[pos[i]][pos[i+1]]);
            f[!(i&1)][i][k]=min(f[!(i&1)][i][k],f[i&1][j][k]+dis[pos[j]][pos[i+1]]);
            f[!(i&1)][i][j]=min(f[!(i&1)][i][j],f[i&1][j][k]+dis[pos[k]][pos[i+1]]);
        }
//      for(int j=1;j<=i;j++){for(int k=1;k<j;k++)printf("%d ",f[!(i&1)][j][k]);puts("");}puts("");
    }
    for(int j=1;j<m;j++)for(int k=1;k<j;k++)res=min(res,f[m&1][j][k]);
    printf("%d\n",res);
    return 0;
} 

思路3.发现O(m^3)只能拿到50\%。似乎只有最后两维可以优化成n^2的。

我们设f[i][j][k]表示：当前某一辆车在第i家公司（还是1000家那个！）剩下两辆车分别在第j和第k个收件地点（是200家那个！）。

复杂度为O(mn^2)。

这是正解尽管出题人丧心病狂卡长只有70\%但是开个O3然后卡卡长就过了。

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,dis[210][210],f[2][1010][1010],pos[1010],m,res=0x3f3f3f3f;
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
    if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n);
    for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)read(dis[i][j]);
    memset(f,0x3f3f3f3f,sizeof(f)),f[1][2][1]=0;
    pos[++m]=1,pos[++m]=2,pos[++m]=3;
    while(scanf("%d",&pos[++m])!=EOF);
    for(register int i=3;i<m;i++){
        for(register int j=1;j<=n;j++)for(register int k=1;k<=n;k++)f[!(i&1)][j][k]=0x3f3f3f3f;
        for(register int j=1;j<=n;j++)for(register int k=1;k<=n;k++){
            f[!(i&1)][j][k]=min(f[!(i&1)][j][k],f[i&1][j][k]+dis[pos[i]][pos[i+1]]);
            f[!(i&1)][pos[i]][k]=min(f[!(i&1)][pos[i]][k],f[i&1][j][k]+dis[j][pos[i+1]]);
            f[!(i&1)][pos[i]][j]=min(f[!(i&1)][pos[i]][j],f[i&1][j][k]+dis[k][pos[i+1]]);
        }
//      for(int j=1;j<=i;j++){for(int k=1;k<j;k++)printf("%d ",f[!(i&1)][j][k]);puts("");}puts("");
    }
    for(register int j=1;j<=n;j++)for(register int k=1;k<=n;k++)res=min(res,f[m&1][j][k]);
    print(res);
    return 0;
} 

II.[HAOI2010]计数

我不得不吐槽出题人的语文实在太……那个了。

翻译一下：给你一个数，求它是全排列中第几个。

为什么呢？我们看一下给定的那个\{1,2\}的例子。显然，在任何合法的数中，所有的非零数的出现次数，在每个数中都是相同的。如果我们允许前导零，那么所有的0的出现次数也都相同了。（删去0可以看作将0移到了开头）

我们考虑借鉴数位DP的思想：从高位向低位枚举，并考虑当前这位填入比原数小的数还是和原数相同的数。

如果填入一个比它小的数，那么后面的位就可以全排列了。

考虑每个数i共出现了cnt_i次，所有数总共出现了tot次。

数字0可以在这tot个位置里面随便填，共C_{tot}^{cnt_0}种方案。

数字1可以在剩下tot-cnt_0个位置里面随便填，共C_{tot-cnt_0}^{cnt_1}种方案。

以此类推。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,num[100],cnt[10],C[100][100],res;
char s[100];
int calc(int tot){
    int ans=1;
    for(int i=0;i<10;i++)ans*=C[tot][cnt[i]],tot-=cnt[i];
    return ans;
}
signed main(){
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=0;i<=n;i++)C[i][0]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
//  for(int i=0;i<=n;i++){for(int j=0;j<=i;j++)printf("%d ",C[i][j]);puts("");}
    for(int i=1;i<=n;i++)num[i]=s[i]-'0',cnt[num[i]]++;
    for(int i=1;i<=n;i++){
        for(int j=0;j<num[i];j++){
            if(!cnt[j])continue;
            cnt[j]--;
            res+=calc(n-i);
            cnt[j]++;
        }
        cnt[num[i]]--;
    }
    printf("%lld\n",res);
    return 0;
}

III.[SCOI2009]粉刷匠

所有的DP，只要式子一推出来（不管复杂度），那就很简单了，因为优化是成千上万种的……

思路1.我们考虑设f[i][j][k]表示：当前DP到第i块木板的第j个位置，共涂了k次，所能获得的最大收益。因为还要枚举当前这次涂是从哪到哪的，因此复杂度为O(NM^2T)，实际90\%。在实际操作中，第一维可以省略。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t,f[100][5000],res[100][100][2],ans;
char s[100];
int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int l=1;l<=n;l++){
        scanf("%s",s+1);
        for(int i=1;i<=m;i++)for(int j=i;j<=m;j++)res[i][j][0]=res[i][j-1][0]+(s[j]=='0'),res[i][j][1]=res[i][j-1][1]+(s[j]=='1');
        for(int i=0;i<=t;i++)f[0][i]=f[m][i];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=t;j++){
                f[i][j]=0;
                for(int k=0;k<i;k++)f[i][j]=max(f[i][j],f[k][j-1]+max(res[k+1][i][0],res[k+1][i][1]));
            }
        }
    }
    for(int i=1;i<=t;i++)ans=max(ans,f[m][i]);
    printf("%d\n",ans);
    return 0;
}

虽然开个O2甚至只是单纯卡卡长也一样能过，但是介于十年前评测姬的蜜汁速度，我们思考还有没有优化复杂度的余地。

思路2.我们考虑设f[i][j][k][0/1/2]表示：

当前DP到第i块木板的第j个位置，共涂了k次，当前这个位置的状态是0/1/2。

其中，状态0意为涂上了颜色0，状态1意为涂上了颜色1，状态2意为啥也没涂。

因为这种方法不需要枚举上一次的断点，因此复杂度是O(NMT)的。老样子，第一维可以砍掉。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t,f[100][5000][3],res;
char s[100];
int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int l=1;l<=n;l++){
        scanf("%s",s+1);
        for(int i=0;i<=t;i++)f[0][i][2]=max(max(f[m][i][0],f[m][i][1]),f[m][i][2]);
        for(int i=1;i<=m;i++){
            for(int j=1;j<=t;j++){
                f[i][j][2]=max(max(f[i-1][j][0],f[i-1][j][1]),f[i-1][j][2]);
                f[i][j][1]=max(max(f[i-1][j-1][0],f[i-1][j][1]),f[i-1][j-1][2])+(s[i]=='0');
                f[i][j][0]=max(max(f[i-1][j][0],f[i-1][j-1][1]),f[i-1][j-1][2])+(s[i]=='1');
            }
        }
    }
    for(int i=1;i<=t;i++)res=max(max(res,f[m][i][2]),max(f[m][i][0],f[m][i][1]));
    printf("%d\n",res);
    return 0;
}

IV.[SCOI2003]字符串折叠

一眼区间DP。

设f[i][j]表示：将区间[i,j]内的所有东西压一起的最短长度。

显然，有两种方法：

1.在中间一刀劈开，然后拼一起。

2.找到它的循环节，然后把整个串压一起。

至于找循环节吗……枚举循环节长度，然后无脑哈希一下。

注意，你可能会压出类似于10(AB)这种东西，记得10是两位数！！！

代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
    ull val1,val2;
    int len;
    HASH(){
        val1=val2=0ull;
        len=0;
    }
    HASH(char ip){
        val1=val2=ip;
        len=1;
    }
    friend HASH operator +(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1*pov1[y.len]+y.val1;
        z.val2=x.val2*pov2[y.len]+y.val2;
        z.len=x.len+y.len;
        return z;
    }
    friend HASH operator -(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1-y.val1*pov1[x.len-y.len];
        z.val2=x.val2-y.val2*pov2[x.len-y.len];
        z.len=x.len-y.len;
        return z;
    }
    friend bool operator ==(const HASH &x,const HASH &y){
        if(x.len!=y.len)return false;
        if(x.val1!=y.val1)return false;
        if(x.val2!=y.val2)return false;
        return true;
    }
}hs[110];
int calc(int x){
    int res=0;
    while(x)res++,x/=10;
    return res;
}
int main(){
    scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
    pov1[0]=pov2[0]=1;
    for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
    for(int i=1;i<=n;i++)hs[i]=hs[i-1]+HASH(s[i]),f[i][i]=1;
    for(int l=2;l<=n;l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            for(int k=1;k<l;k++){
                if(l%k)continue;
                if((hs[j]-hs[i+k-1])==(hs[j-k]-hs[i-1]))f[i][j]=min(f[i][j],f[i][i+k-1]+2+calc(l/k));
            }
        }
    }
//  for(int i=1;i<=n;i++){for(int j=i;j<=n;j++)printf("%d ",f[i][j]);puts("");}
    printf("%d\n",f[1][n]);
    return 0;
}

V.[SCOI2007]压缩

这种DP状态需要考虑到各种状态的题最讨厌了……

思路1.设f[i][j]表示将区间[i,j]里面所有东西压一起的最小代价

有两种转移：

1. 砍成两段拼一起

2. 样例里面这种方法，MaRR=aaaa 这种倍增法

然后我就写出了这样的代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
    ull val1,val2;
    int len;
    HASH(){
        val1=val2=0ull;
        len=0;
    }
    HASH(char ip){
        val1=val2=ip;
        len=1;
    }
    friend HASH operator +(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1*pov1[y.len]+y.val1;
        z.val2=x.val2*pov2[y.len]+y.val2;
        z.len=x.len+y.len;
        return z;
    }
    friend HASH operator -(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1-y.val1*pov1[x.len-y.len];
        z.val2=x.val2-y.val2*pov2[x.len-y.len];
        z.len=x.len-y.len;
        return z;
    }
    friend bool operator ==(const HASH &x,const HASH &y){
        if(x.len!=y.len)return false;
        if(x.val1!=y.val1)return false;
        if(x.val2!=y.val2)return false;
        return true;
    }
    friend bool operator !=(const HASH &x,const HASH &y){
        return !(x==y);
    }
}hs[110];
bool che(int ip){
    return ip==(ip&-ip);
}
int main(){
    scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
    pov1[0]=pov2[0]=1;
    for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
    for(int i=1;i<=n;i++)hs[i]=hs[i-1]+HASH(s[i]),f[i][i]=1;
    for(int l=2;l<=n;l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            for(int k=1;k<l;k++){
                if(l%k)continue;
                if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
                if(!che(l/k))continue;
//              printf("%d %d %d\n",i,j,l/k);
                f[i][j]=min(f[i][j],f[i][i+k-1]+__builtin_ctz(l/k)+(i!=1));
            }
        }
    }
//  for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
    printf("%d\n",f[1][n]);
    return 0;
}

一交，WA，40\%。

怎么回事？

我费尽千辛万苦，找到一组hack数据：

xabababababab

按照我之前的这种压法，会压出来xMMabRabR这种东西。因为这时区间DP，按照我之前的思路，是按照括号的顺序压的：

x(M(MabR)abR)

因此，相同的左端点，如果已经有了一个M，就不用重复有M了。

我们设一个新状态f[i][j][0/1]表示：将区间[i,j]压一起，左端点有无M的状态是[0/1]。

然后写出来这样的东西：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
    ull val1,val2;
    int len;
    HASH(){
        val1=val2=0ull;
        len=0;
    }
    HASH(char ip){
        val1=val2=ip;
        len=1;
    }
    friend HASH operator +(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1*pov1[y.len]+y.val1;
        z.val2=x.val2*pov2[y.len]+y.val2;
        z.len=x.len+y.len;
        return z;
    }
    friend HASH operator -(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1-y.val1*pov1[x.len-y.len];
        z.val2=x.val2-y.val2*pov2[x.len-y.len];
        z.len=x.len-y.len;
        return z;
    }
    friend bool operator ==(const HASH &x,const HASH &y){
        if(x.len!=y.len)return false;
        if(x.val1!=y.val1)return false;
        if(x.val2!=y.val2)return false;
        return true;
    }
    friend bool operator !=(const HASH &x,const HASH &y){
        return !(x==y);
    }
}hs[110];
bool che(int ip){
    return ip==(ip&-ip);
}
int main(){
    scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
    pov1[0]=pov2[0]=1;
    for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
    for(int i=1;i<=n;i++){
        hs[i]=hs[i-1]+HASH(s[i]);
        f[i][i][0]=1;
        f[i][i][1]=1+(i!=1);
    }
    for(int l=2;l<=n;l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            for(int k=i;k<j;k++)f[i][j][0]=min(f[i][j][0],f[i][k][0]+min(f[k+1][j][0],f[k+1][j][1])),f[i][j][1]=min(f[i][j][1],f[i][k][1]+min(f[k+1][j][0],f[k+1][j][1]));
            for(int k=1;k<l;k++){
                if(l%k)continue;
                if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
                if(!che(l/k))continue;
//              printf("%d %d %d\n",i,j,l/k);
                f[i][j][1]=min(f[i][j][1],min(f[i][i+k-1][0]+1,f[i][i+k-1][1])+__builtin_ctz(l/k));
            }
        }
    }
//  for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
    printf("%d\n",f[1][n][1]);
    return 0;
}
//xabababababab

一交，WA，70\%。

然后我想了想，那种倍增的合并法也可以并入（左端点已经有了M）的情形。

然后我改成了这样的代码（这种情形实际上哈希都没必要了）

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
    ull val1,val2;
    int len;
    HASH(){
        val1=val2=0ull;
        len=0;
    }
    HASH(char ip){
        val1=val2=ip;
        len=1;
    }
    friend HASH operator +(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1*pov1[y.len]+y.val1;
        z.val2=x.val2*pov2[y.len]+y.val2;
        z.len=x.len+y.len;
        return z;
    }
    friend HASH operator -(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1-y.val1*pov1[x.len-y.len];
        z.val2=x.val2-y.val2*pov2[x.len-y.len];
        z.len=x.len-y.len;
        return z;
    }
    friend bool operator ==(const HASH &x,const HASH &y){
        if(x.len!=y.len)return false;
        if(x.val1!=y.val1)return false;
        if(x.val2!=y.val2)return false;
        return true;
    }
    friend bool operator !=(const HASH &x,const HASH &y){
        return !(x==y);
    }
}hs[110];
int main(){
    scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
    pov1[0]=pov2[0]=1;
    for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
    for(int i=1;i<=n;i++){
        hs[i]=hs[i-1]+HASH(s[i]);
        f[i][i][0]=1;
        f[i][i][1]=1+(i!=1);
    }
    for(int l=2;l<=n;l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            for(int k=i;k<j;k++)f[i][j][0]=min(f[i][j][0],f[i][k][0]+min(f[k+1][j][0],f[k+1][j][1])),f[i][j][1]=min(f[i][j][1],f[i][k][1]+min(f[k+1][j][0],f[k+1][j][1]));
            if(l&1)continue;
            int k=l>>1;
            if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
            f[i][j][1]=min(f[i][j][1],min(f[i][i+k-1][0]+1,f[i][i+k-1][1])+1);
        }
    }
//  for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
    printf("%d\n",f[1][n][1]);
    return 0;
}
//xabababababab
//xabcabcxabcabc

一交，WA，还是70\%。

我费劲千辛万苦，终于找到另一组hack数据：

xabcabcxabcabc

按照我之前的思路，会压出来这样的东西：

xMabcRR

因为我的程序是这样考虑的：

x(MabcR)R，根本没有考虑内部的情况

因此还要额外再加一维，表示该串内部有无M：

我们现在得到的是状态f[i][j][0/1][0/1]。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
char s[110];
int n,f[110][110][2][2];
ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];
struct HASH{
    ull val1,val2;
    int len;
    HASH(){
        val1=val2=0ull;
        len=0;
    }
    HASH(char ip){
        val1=val2=ip;
        len=1;
    }
    friend HASH operator +(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1*pov1[y.len]+y.val1;
        z.val2=x.val2*pov2[y.len]+y.val2;
        z.len=x.len+y.len;
        return z;
    }
    friend HASH operator -(const HASH &x,const HASH &y){
        HASH z;
        z.val1=x.val1-y.val1*pov1[x.len-y.len];
        z.val2=x.val2-y.val2*pov2[x.len-y.len];
        z.len=x.len-y.len;
        return z;
    }
    friend bool operator ==(const HASH &x,const HASH &y){
        if(x.len!=y.len)return false;
        if(x.val1!=y.val1)return false;
        if(x.val2!=y.val2)return false;
        return true;
    }
    friend bool operator !=(const HASH &x,const HASH &y){
        return !(x==y);
    }
}hs[110];
int main(){
    scanf("%s",s+1),memset(f,0x3f3f3f3f,sizeof(f)),n=strlen(s+1);
    pov1[0]=pov2[0]=1;
    for(int i=1;i<=n;i++)pov1[i]=pov1[i-1]*sd1,pov2[i]=pov2[i-1]*sd2;
    for(int i=1;i<=n;i++){
        hs[i]=hs[i-1]+HASH(s[i]);
        f[i][i][0][0]=1;
        f[i][i][1][0]=1+(i!=1);
    }
    for(int l=2;l<=n;l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            for(int k=i;k<j;k++){
                f[i][j][0][0]=min(f[i][j][0][0],f[i][k][0][0]+f[k+1][j][0][0]);
                f[i][j][1][0]=min(f[i][j][1][0],f[i][k][1][0]+f[k+1][j][0][0]);
                f[i][j][0][1]=min(f[i][j][0][1],min(f[i][k][0][1],f[i][k][0][0])+min(min(f[k+1][j][0][0],f[k+1][j][0][1]),min(f[k+1][j][1][0],f[k+1][j][1][1])));
                f[i][j][1][1]=min(f[i][j][1][1],min(f[i][k][1][1],f[i][k][1][0])+min(min(f[k+1][j][0][0],f[k+1][j][0][1]),min(f[k+1][j][1][0],f[k+1][j][1][1])));
            }
            if(l&1)continue;
            int k=l>>1;
            if((hs[j]-hs[i+k-1])!=(hs[j-k]-hs[i-1]))continue;
            f[i][j][1][0]=min(f[i][j][1][0],min(f[i][i+k-1][0][0]+1,f[i][i+k-1][1][0])+1);
        }
    }
//  for(int l=1;l<=n;l++){for(int i=1,j=i+l-1;j<=n;i++,j++)printf("%d ",f[i][j]);puts("");}
    printf("%d\n",min(f[1][n][1][0],f[1][n][1][1]));
    return 0;
}
//xabababababab
//xabcabcxabcabc

VI.[HAOI2008]玩具取名

状压一下。

我们令f[i][j]为：区间[i,j]的串，能转移到字母的状态（是个 bitmask ）

至于转移吗……劈开拼一起即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int m[4],n,tr[4][4],f[210][210];
int tran(char ip){
    if(ip=='W')return 0;
    if(ip=='I')return 1;
    if(ip=='N')return 2;
    if(ip=='G')return 3;
}
char s[210];
int main(){
    for(int i=0;i<4;i++)scanf("%d",&m[i]);
    for(int i=0;i<4;i++)for(int j=0;j<m[i];j++)scanf("%s",s),tr[tran(s[0])][tran(s[1])]|=(1<<i);
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=1;i<=n;i++)f[i][i]=(1<<tran(s[i]));
    for(int l=2;l<=n;l++)for(int i=1,j=i+l-1;j<=n;i++,j++)for(int k=i;k<j;k++)for(int a=0;a<4;a++)for(int b=0;b<4;b++){
        if(!(f[i][k]&(1<<a)))continue;
        if(!(f[k+1][j]&(1<<b)))continue;
        f[i][j]|=tr[a][b];
    }
    if(f[1][n]&(1<<0))putchar('W');
    if(f[1][n]&(1<<1))putchar('I');
    if(f[1][n]&(1<<2))putchar('N');
    if(f[1][n]&(1<<3))putchar('G');
    if(!f[1][n])puts("The name is wrong!");
    return 0;
}

VII.[SDOI2009]Bill的挑战

第一眼看上去不会做。第二眼发现n\leq 15直觉状压。第三眼算算复杂度发现OK，然后就没问题了。

我们设f[i][j]表示：

当前DP到了第i位，

所有串的匹配成功的状态是j，

的方案数。

通过预处理一个状压数组mat[i][j]表示第i位填入字符j的匹配结果，我们可以在复杂度O(TAlen2^n)范围内跑过。其中T是数据组数，A是字符集大小（26），len是串长，n是串数。

这是正解，只是毒瘤出题人卡长，不得不吸个臭氧才卡过。

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int mod=1000003;
int T,n,m,S,f[100][1<<15],mat[100][26],MAXN,res;
char s[15][100];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m),MAXN=1<<n,res=0,memset(f,0,sizeof(f)),memset(mat,0,sizeof(mat));
        for(register int i=0;i<n;i++)scanf("%s",s[i]+1);
        S=strlen(s[0]+1);
        for(register int i=1;i<=S;i++)for(register int j=0;j<26;j++)for(register int k=0;k<n;k++)if(s[k][i]=='?'||s[k][i]==j+'a')mat[i][j]|=1<<k;
        f[0][MAXN-1]=1;
        for(register int i=0;i<S;i++)for(register int j=0;j<MAXN;j++)for(register int k=0;k<26;k++)(f[i+1][j&mat[i+1][k]]+=f[i][j])%=mod;
        for(register int i=0;i<MAXN;i++)if(__builtin_popcount(i)==m)(res+=f[S][i])%=mod;
        printf("%d\n",res);
    }
    return 0;
}

VIII.CF149D Coloring Brackets

考虑设f[i][j][k=0/1/2][l=0/1/2]表示：将区间[i,j]里的东西染色，左端染上颜色k，右端染上颜色l（0为红，1为蓝，2不染）的方案数。

因为这个n是700，n^3似乎过不了，考虑n^2的区间DP。

我们首先关于每个括号找出它匹配的位置。然后，约定只有合法的子串（连续的）的DP值是有效的，不合法的子串的DP值都为0。

当我们要求出[i,j]的DP值时，

1. 如果在位置[i,j]上的括号本身就是匹配的，直接从[i+1,j-1]转移过来；

2. 否则，既然这个子串是合法的，那唯一的构成方式就是拼接（例如()()）。直接从某个位置断开（比如说从右边界的匹配位置那边断开）拼一起即可。

复杂度为O((C+1)^4*n^2)，其中C是颜色数（本题中为2）。

代码:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int mat[710],n,f[710][710][3][3],res;
char s[710];
stack<int>stk;
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='(')stk.push(i);
        else mat[stk.top()]=i,mat[i]=stk.top(),stk.pop();
    }
    for(int i=1;i<n;i++)if(mat[i]==i+1)f[i][i+1][0][2]=f[i][i+1][2][0]=f[i][i+1][1][2]=f[i][i+1][2][1]=1;
    for(int l=4;l<=n;l+=2)for(int i=1,j=i+l-1;j<=n;i++,j++){
        if(s[i]!='('||s[j]!=')')continue;
        if(mat[i]==j){
            for(int a=0;a<3;a++)for(int b=0;b<3;b++){
                if(a==b)continue;
                if(a!=2&&b!=2)continue;
                for(int c=0;c<3;c++)for(int d=0;d<3;d++){
                    if(a!=2&&c!=2&&a==c)continue;
                    if(b!=2&&d!=2&&b==d)continue;
                    (f[i][j][a][b]+=f[i+1][j-1][c][d])%=mod;
                }
            }
        }else{
            int k=mat[j];
            for(int a=0;a<3;a++)for(int b=0;b<3;b++)for(int c=0;c<3;c++)for(int d=0;d<3;d++){
                if(b!=2&&c!=2&&b==c)continue;
                f[i][j][a][d]=(1ll*f[i][k-1][a][b]*f[k][j][c][d]+f[i][j][a][d])%mod;
            }       
        }
    }
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)(res+=f[1][n][i][j])%=mod;
    printf("%d\n",res);
    return 0;
} 

IX.[AHOI2018初中组]球球的排列

论DP的百种用法之一

因为DP必须有一种全面的状态，但是这道题……似乎排列等等问题都不是DP擅长处理的地方。

首先分析性质。我们发现，这种不能放在一起的关系具有传递性。因为如果xy=a^2,xz=b^2，那么yz=\dfrac{(xy)(yz)}{x^2}=\dfrac{a^2b^2}{x^2}=\Big(\dfrac{ab}{x}\Big)^2。

具有传递性的话，我们就会发现，所有不能放在一起的位置，构成了多个团（完全图）。

我们就想着把每个团里的所有球都染上同一种颜色，则相同颜色的球不能紧贴在一起。

则我们现在将问题转换为：给你n个染了色的球，相同的球不能放一起，求排列数。

考虑将这些球按照颜色排序，这样便有了一个合理的（可以抽象出状态的）DP顺序。

我们设f[i][j][k]表示：

当前DP到第i位，

有两个球放在一起，它们的颜色相同，并且颜色与第i位的球不同，这样的对共有j个，

有两个球放在一起，它们的颜色相同，并且颜色与第i位的球相同，这样的对共有k个，

的方案数。

因为我们已经排过序，因此颜色相同的球必定紧贴。

1.第 i 位的球和第 i-1 位的球颜色不同。

则DP状态的第三维（即k）必为0，因为不存在在它之前并且和它颜色相同的球。我们只需要枚举第二维j。

1.1.我们将这个球放在两个颜色不同的球之间。

我们枚举一个k'，表示上一个球所代表的颜色中颜色相同且紧贴的对共有k'个（k'\in[0,j]）。

则有f[i][j][0]+=f[i-1][j-k'][k']*(i-j)，因为共有j-k'个相邻且相同且和上一个球的颜色不同的位置，并且共有i-j个可以放球的位置。

1.2.我们将这个球放在两个颜色相同的球之间。

我们仍然枚举一个k'，意义相同。这时，k'\in[0,j+1]。

则有f[i][j][0]+=f[i-1][j-k'+1][k']*(j+1)。因为放入这个球后就拆开了一对球，因此原来共有 j+1 对这样的球。

2.第 i 位的球和第 i-1 位的球颜色相同。

我们需要枚举剩余两维j,k。并且，设在第i位之前，有cnt个和第i位相同的位置。

2.1.我们将这个球放在某个和这个球颜色相同的球旁边。

则共有2*cnt-(k-1)个这样的位置。

因此有f[i][j][k]+=f[i-1][j][k-1]*(2*cnt-(k-1))。

2.2.我们将这个球放在两个颜色相同的球之间。

同1.2，有f[i][j][k]+=f[i-1][j+1][k]*(j+1)。

2.3.我们将这个球放在两个颜色不同且与这个球颜色不同的球之间。

这次操作没有添加或删除任何对，并且共有i-(2*cnt-k)-j个位置。

因此有f[i][j][k]+=f[i-1][j][k]*(i-(cnt*2-k)-j)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int n,num[310],dsu[310],f[2][310][310];
vector<int>v;
int find(int x){
    return dsu[x]==x?x:dsu[x]=find(dsu[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    dsu[x]=y;
}
bool che(ll ip){
    ll tmp=sqrt(ip)+0.5;
    return tmp*tmp==ip;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]),dsu[i]=i;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(che(1ll*num[i]*num[j]))merge(i,j);
    for(int i=1;i<=n;i++)dsu[i]=find(i);
    sort(dsu+1,dsu+n+1);
    f[0][0][0]=1;
    for(int i=1,cnt;i<=n;i++){
        memset(f[i&1],0,sizeof(f[i&1]));
        if(dsu[i]!=dsu[i-1]){
            cnt=0;
            for(int j=0;j<i;j++){
                for(int k=0;k<=j;k++)f[i&1][j][0]=(1ll*f[!(i&1)][j-k][k]*(i-j)+f[i&1][j][0])%mod;//if we put it between two balls of different colours
                for(int k=0;k<=j+1;k++)f[i&1][j][0]=(1ll*f[!(i&1)][j-k+1][k]*(j+1)+f[i&1][j][0])%mod;//if we put it between two balls of the same colours
            }
        }else{
            for(int j=0;j<i;j++){
                for(int k=1;k<=cnt;k++)f[i&1][j][k]=(1ll*f[!(i&1)][j][k-1]*(cnt*2-(k-1))+f[i&1][j][k])%mod;//if we put it next to a ball of the same colour
                for(int k=0;k<=cnt;k++)f[i&1][j][k]=(1ll*f[!(i&1)][j+1][k]*(j+1)+f[i&1][j][k])%mod;//if we put it between two balls of the same colours
                for(int k=0;k<=cnt;k++)f[i&1][j][k]=(1ll*f[!(i&1)][j][k]*(i-(cnt*2-k)-j)+f[i&1][j][k])%mod;//if we put it between two balls of different colours
            }
        }
        cnt++;
    }
    printf("%d\n",f[n&1][0][0]);
    return 0;
}

X.[SCOI2008]着色方案

双倍经验，双倍快乐

可以看出这题直接是上一题的无编号版，直接套上一题的板子，乘上逆元的倒数直接水过，还轻轻松松完虐正解（五维暴力DP）

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int n,m,num[310],dsu[310],f[2][310][310],res,fac[310];
int ksm(int x,int y){
    int z=1;
    for(;y;x=(1ll*x*x)%mod,y>>=1)if(y&1)z=(1ll*x*z)%mod;
    return z;
}
int main(){
    scanf("%d",&m);
    for(int i=1,x;i<=m;i++){
        scanf("%d",&num[i]);
        for(int j=1;j<=num[i];j++)dsu[++n]=i;
    }
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=(1ll*fac[i-1]*i)%mod;
    f[0][0][0]=1;
    for(int i=1,cnt;i<=n;i++){
        memset(f[i&1],0,sizeof(f[i&1]));
        if(dsu[i]!=dsu[i-1]){
            cnt=0;
            for(int j=0;j<i;j++){
                for(int k=0;k<=j;k++)f[i&1][j][0]=(1ll*f[!(i&1)][j-k][k]*(i-j)+f[i&1][j][0])%mod;//if we put it between two balls of different colours
                for(int k=0;k<=j+1;k++)f[i&1][j][0]=(1ll*f[!(i&1)][j-k+1][k]*(j+1)+f[i&1][j][0])%mod;//if we put it between two balls of the same colours
            }
        }else{
            for(int j=0;j<i;j++){
                for(int k=1;k<=cnt;k++)f[i&1][j][k]=(1ll*f[!(i&1)][j][k-1]*(cnt*2-(k-1))+f[i&1][j][k])%mod;//if we put it next to a ball of the same colour
                for(int k=0;k<=cnt;k++)f[i&1][j][k]=(1ll*f[!(i&1)][j+1][k]*(j+1)+f[i&1][j][k])%mod;//if we put it between two balls of the same colours
                for(int k=0;k<=cnt;k++)f[i&1][j][k]=(1ll*f[!(i&1)][j][k]*(i-(cnt*2-k)-j)+f[i&1][j][k])%mod;//if we put it between two balls of different colours
            }
        }
        cnt++;
    }
    res=f[n&1][0][0];
    for(int i=1;i<=m;i++)res=(1ll*res*ksm(fac[num[i]],mod-2))%mod;
    printf("%d\n",res);
    return 0;
}

当然这么就水过一道题好像有点不好意思哈

因此额外再介绍一种方法，复杂度最劣应该是O(n^3)的，其中n是木块数量。

我们设num[i]表示第i种颜色有多少个，sum[i]为前i种颜色有多少个。

因为这题无编号，我们可以考虑简化一维：设f[i][j]表示：

前i种颜色（！！！）

涂了前sum[i]块，

并且有j对相邻同色对的方案数。

我们采取刷表法进行DP。

考虑由f[i][j]推出f[i+1][?]。

我们枚举一个k\in\Big[1,num[i+1]\Big]，表示我们将num[i+1]分成k段连续的同色木块。

我们再枚举一个l\in\Big[0,\min(j,k)\Big]，表示我们从这k段木块中，抽出l段木块塞在两段颜色相同但相邻的木块中。

首先，依据隔板法（小学奥数），共有\large C_{num[i+1]-1}^{k-1}中合法的分割方案；

一共有sum[i]-j+1个颜色不同的相邻位置，因此这j-l段放入颜色相同的位置的木块共有\large C_{sum[i]-j+1}^{j-l}种放法。

一共有j个颜色相同的相邻位置，共有C_j^l种放法。

则总方案数为\large C_{num[i+1]-1}^{k-1}*C_{sum[i]-j+1}^{j-l}*C_j^l*f[i][j]。

等等，这一大坨是往哪里更新去的？

是往f\Big[i+1\Big]\Big[j+num[i+1]-k-l\Big]更新的。原本应该增加num[i+1]-1段相邻的，现在聚合成了k段，减少了k-1段；有l段放偏了，又减少了l段。

代码（压 行 带 师）：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int f[20][100],n,num[20],sum[20],C[100][100];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]),sum[i]=sum[i-1]+num[i];
    for(int i=0;i<=sum[n];i++)C[i][0]=1;
    for(int i=1;i<=sum[n];i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    f[1][num[1]-1]=1;
    for(int i=1;i<n;i++)for(int j=0;j<sum[i];j++)for(int k=1;k<=num[i+1];k++)for(int l=0;l<=min(k,j);l++)f[i+1][j-k+num[i+1]-l]=(1ll*f[i][j]*C[num[i+1]-1][k-1]%mod*C[sum[i]-j+1][k-l]%mod*C[j][l]%mod+f[i+1][j-k+num[i+1]-l])%mod;
    printf("%d\n",f[n][0]);
    return 0;
}

XI.[SHOI2007]书柜的尺寸

排序是各类DP题中只要出现了物品这个意象后的常客。

我们首先将书按照高度递减排序。这样，一个书柜的高度，就是第一本被放进来的书的高度。

设f[i][j][k]表示：DP到第i本书，第一层书架的长度为j，第二层书架的长度为k时，整个书柜的最小高度。设sum[i]表示所有书厚度的前缀和。

我们枚举这本书到底是放入第一层、第二层还是第三层（第三层长度为sum[i]-j-k）。

转移分几种情况：

1. 当j=0，即第一层为空时，应该加上h[i]。

2. 当k=0，应该加上h[i]。

3. 当j+k=sum[i]，应该加上h[i]。

答案就是枚举f[n][?][?]统计答案即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int f[2][2110][2110],n,sum[110];
typedef long long ll;
ll res=0x3f3f3f3f3f3f3f3f;
pair<int,int>p[100];
bool cmp(pair<int,int>x,pair<int,int>y){
    return x.first>y.first;
}
int main(){
    scanf("%d",&n),memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d%d",&p[i].first,&p[i].second);
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+p[i].second;
    f[0][0][0]=0;
    for(int i=0;i<n;i++){
        memset(f[!(i&1)],0x3f3f3f3f,sizeof(f[!(i&1)]));
        for(int j=0;j<=sum[i];j++)for(int k=0;j+k<=sum[i];k++){
            f[!(i&1)][j+p[i+1].second][k]=min(f[!(i&1)][j+p[i+1].second][k],f[i&1][j][k]+p[i+1].first*(!j));
            f[!(i&1)][j][k+p[i+1].second]=min(f[!(i&1)][j][k+p[i+1].second],f[i&1][j][k]+p[i+1].first*(!k));
            f[!(i&1)][j][k]=min(f[!(i&1)][j][k],f[i&1][j][k]+p[i+1].first*(!(sum[i]-j-k)));
        }
    }
    for(int i=1;i<sum[n];i++)for(int j=1;i+j<sum[n];j++)res=min(res,1ll*max(max(i,j),sum[n]-i-j)*f[n&1][i][j]);
    printf("%d\n",res);
    return 0;
}

XII.任务安排

斜率优化真\color{black}\colorbox{black}{XX}有意思！！

设t[i]表示原题中的t_i的前缀和，c[i]表示原题中f_i的前缀和，m表示启动时间s。

思路1：n^3DP：

设f[i][j]表示：前i个位置，分成j组，的最快时间。

则有f[i][j]=\min\limits_{k=0}^{i-1}\{f[k][j-1]+(t[i]+m*j)*(c[i]-c[k])\}。

思路2：n^2DP：

观察到我们每在第i个点前多分出一组，则在i后面所有东西的时间都会向后拖m时刻，共计造成m*(c[n]-c[i])点费用，

因此我们可以设f[i]表示前i个位置的最短时间，

则有f[i]=\min\limits_{j=0}^{i-1}\{f[j]+m*(c[n]-c[j])+t[i]*(c[i]-c[j])\}。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[10010],t[10010],c[10010];
int main(){
    scanf("%d%d",&n,&m),memset(f,0x3f3f3f3f,sizeof(f)),f[0]=0;
    for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
    for(int i=1;i<=n;i++)for(int j=0;j<i;j++)f[i]=min(f[i],f[j]+m*(c[n]-c[j])+t[i]*(c[i]-c[j]));
    printf("%d\n",f[n]);
    return 0;
}

思路3：考虑斜率优化。

设j<k<i，且j比k更优。

则有

拆括号

消元

移项并合并

再移

注意因为j<k，且c是前缀和，则c[j]<c[k]。不等式两边除以负数，应该换方向。

最终得到

左边的东西仅与j和k有关；右边的东西是单调的（t也是前缀和）；

因此就可以斜率优化辣。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,t[10100],c[10100],f[10100],q[10100],l,r;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&c[i]),t[i]+=t[i-1],c[i]+=c[i-1];
    for(int i=1;i<=n;i++){
        while(r-l&&(f[q[l]]-f[q[l+1]])>=(c[q[l]]-c[q[l+1]])*(m+t[i]))l++;
        f[i]=f[q[l]]+m*(c[n]-c[q[l]])+t[i]*(c[i]-c[q[l]]);
        while(r-l&&(f[q[r-1]]-f[q[r]])*(c[q[r]]-c[i])>=(f[q[r]]-f[i])*(c[q[r-1]]-c[q[r]]))r--;
        q[++r]=i;
    }
    printf("%d\n",f[n]);
    return 0;
}

XII.[SDOI2012]任务安排

同上一题一样，不过，这题的t_i可能有负数，这就意味着前缀和不再是单调增的！

我们不能再像前一题一样用单调队列维护了——但是因为队尾的单调性仍然存在，我们仍然可以维护上凸包。这就启发我们使用单调栈来维护斜率，并且在单调栈中二分。

我们不妨想一想，如果这个c也有可能是负数怎么办？

代入平均值的定义

暴力展开平方项

分离\Sigma

稍作整合

合并

乘以m^2

右边的等式中，左边是定值（等于总路程的平方）；右边则要我们最小化\sum\limits_{i=1}^ml_i^2。

设f[i][j]表示：前i天内分成了j段的最小平方和。再设s_i表示路程的前缀和。

则有f[i][j]=\min\limits_{k=0}^{i-1}\{f[k][j-1]+(s_i-s_k)^2\}

可以n^2m的进行暴力DP，能拿到60\%。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s[3010],f[3010][3010];
int main(){
    scanf("%d%d",&n,&m),memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
    f[0][0]=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=min(i,m);j++)for(int k=0;k<i;k++)f[i][j]=min(f[i][j],f[k][j-1]+(s[i]-s[k])*(s[i]-s[k]));
    printf("%d\n",m*f[n][m]-s[n]*s[n]);
    return 0;
} 

我们尝试按段数DP，而不是按天数DP。即，在f[i][j]中，优先枚举j。

在枚举j后，我们就可以暂时忽略j这一维了。

我们有f[i]=\min\limits_{j=0}^{i-1}\{F[j]+(s_i-s_j)^2\}。其中，这个F[j]是上一轮DP时的f值，即原本的f[i][j-1]（注意这个j和上面递推式里面的枚举的j不是同一个j）

假设j<k<i，且j比k优，

则有

暴力展开

合并同类项

移项

提一下

除过去（注意s_j-s_k是负的！！！）

左边的东西与i无关；右边的东西单调增；

那不就可以了吗！！！

维护下凸壳，直接斜率优化硬套，完事。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s[3010],f[3010][3010],q[3010],l,r;
int main(){
    scanf("%d%d",&n,&m),memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d",&s[i]),s[i]+=s[i-1];
    f[0][0]=0;
    for(int j=1;j<=m;j++){
        l=r=0;
        for(int i=1;i<=n;i++){
            while(r-l&&f[q[l]][j-1]-f[q[l+1]][j-1]+s[q[l]]*s[q[l]]-s[q[l+1]]*s[q[l+1]]>=2*s[i]*(s[q[l]]-s[q[l+1]]))l++;
            f[i][j]=f[q[l]][j-1]+(s[i]-s[q[l]])*(s[i]-s[q[l]]);
            while(r-l&&(f[q[r-1]][j-1]-f[q[r]][j-1]+s[q[r-1]]*s[q[r-1]]-s[q[r]]*s[q[r]])*(s[q[r]]-s[i])>=(f[q[r]][j-1]-f[i][j-1]+s[q[r]]*s[q[r]]-s[i]*s[i])*(s[q[r-1]]-s[q[r]]))r--;
            q[++r]=i; 
        }
    }
    printf("%d\n",m*f[n][m]-s[n]*s[n]);
    return 0;
} 

XIV.[SDOI2013]保护出题人

这题好像不算DP……但是涉及到斜率和凸包的题都是好题

因为这题要求是确保没有任何一个姜丝能活着走到门口，

所以设血量的前缀和为s，每两只姜丝间距离为m，

则对于 \forall i ，

都应有ans_i=\max\limits_{j=0}^{i-1}\{\dfrac{s_i-s_j}{x_i+(i-j-1)*m}\}

其中，分母是第 j+1 只姜丝距离门的距离，分子是第i到第j+1姜丝的总血量。

这样便能拿到50\%！！

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s[100100];
double res,ans;
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1,x;i<=n;i++){
        scanf("%lld%lld",&s[i],&x),s[i]+=s[i-1],res=0;
        for(int j=0;j<i;j++)res=max(res,1.0*(s[i]-s[j])/(x+(i-j-1)*m));
        ans+=res;
    }
    printf("%.0lf\n",ans);
    return 0;
}

我们将这个东西变成斜率的形式：

可以将其看作是\Big(s_i,x_i+im\Big)与\Big(s_j,m(j+1)\Big)的斜率。

即

前者我们没法管它；但是后者，我们是可以维护下凸壳的（因为对于不同的i，后面的东西是相同的）。用单调栈维护并二分查找出斜率的最大值（实际上对于这种单峰函数应该写三分来着的……但是如果三分分的那两个点都在一起那不就是二分吗），并统计答案即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define mp make_pair 
int n,m,s[100100],tp;
double res,ans;
double slope(pii u,pii v){//ask for the slope from u to v
    return 1.0*(v.y-u.y)/(v.x-u.x);
}
pii stk[100100];
signed main(){
    scanf("%lld%lld",&n,&m),stk[0]=mp(m,0);
    for(int i=1,x;i<=n;i++){
        scanf("%lld%lld",&s[i],&x),s[i]+=s[i-1];
        int l=0,r=tp,qwq=0;
        pii tmp=mp(x+i*m,s[i]);
        while(l<=r){
            int mid=(l+r)>>1;
            if(slope(stk[mid],tmp)<slope(stk[mid-1],tmp))r=mid-1;
            else qwq=mid,l=mid+1;
        }
        res=slope(stk[qwq],tmp);
        tmp=mp((i+1)*m,s[i]);
        while(tp&&slope(stk[tp-1],tmp)>=slope(stk[tp],tmp))tp--;
        stk[++tp]=tmp;
        ans+=res;
    }
    printf("%.0lf\n",ans);
    return 0;
}

XV.[JSOI2009]火星藏宝图

一个非常显然的结论：在最优方案中，路径上的任意两个点所构成的矩形内部一定不存在其它点。不然的化，在这个其它的点多停留一下一定不会更差。

因为a^2+b^2<(a+b)^2。

但是，就算想到这个，我也得不出什么好的转移方式

考虑将所有岛屿按照行优先，如果行相同就按列优先进行排序。这样，对于任何一个岛i，所有编号小于i的且列比它小的岛都是可转移的。

而在所有列相同的岛中，行最大的那个一定是最优的。

因此我们可以针对每行维护一个列数最大的点（类似于桶），每次只需要遍历这些桶进行转移即可。

复杂度O(nm)，卡卡就卡过去了。

代码：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int n,m,tri[1010],f[200100];
struct node{
    int x,y,v;
    friend bool operator <(const node &x,const node &y){
        if(x.x!=y.x)return x.x<y.x;
        return x.y<y.y;
    }
}is[200100];
inline void read(int &x){
    x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<=9)putchar('0'+x);
    else print(x/10),putchar('0'+x%10);
}
int main(){
    read(n),read(m);
    for(register int i=1;i<=n;i++)read(is[i].x),read(is[i].y),read(is[i].v);
    sort(is+1,is+n+1);
    tri[1]=1;
    f[1]=is[1].v;
    for(register int i=2;i<=n;i++){
        f[i]=f[1]-(is[i].x-1)*(is[i].x-1)-(is[i].y-1)*(is[i].y-1);
        for(register int j=1;j<=is[i].y;j++)if(tri[j])f[i]=max(f[i],f[tri[j]]-(is[i].x-is[tri[j]].x)*(is[i].x-is[tri[j]].x)-(is[i].y-is[tri[j]].y)*(is[i].y-is[tri[j]].y));
        f[i]+=is[i].v;
        tri[is[i].y]=i;
    }
    print(f[n]);
    return 0;
}

XVI.[HDU3507]Print Article

没什么好说的，这题比任务安排还水，随便推推完事。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s[500100],f[500100],q[500100],l,r;
signed main(){
    while(scanf("%lld%lld",&n,&m)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%lld",&s[i]);
            if(!s[i]){i--,n--;continue;}
            s[i]+=s[i-1];
        }
//      for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
        l=r=0;
        for(int i=1;i<=n;i++){
            while(r-l&&f[q[l]]-f[q[l+1]]+s[q[l]]*s[q[l]]-s[q[l+1]]*s[q[l+1]]>=2*s[i]*(s[q[l]]-s[q[l+1]]))l++;
            f[i]=f[q[l]]+m+(s[i]-s[q[l]])*(s[i]-s[q[l]]);
            while(r-l&&(f[q[r-1]]-f[q[r]]+s[q[r-1]]*s[q[r-1]]-s[q[r]]*s[q[r]])*(s[q[r]]-s[i])>=(f[q[r]]-f[i]+s[q[r]]*s[q[r]]-s[i]*s[i])*(s[q[r-1]]-s[q[r]]))r--;
            q[++r]=i;
        }
        printf("%lld\n",f[n]);
    }
    return 0;
}

XVII.CF311B Cats Transport

推式子时间到~~~

我们首先对题目中的d_i做前缀和，求出每座山距离原点距离；

然后对于第i只猫，如果一个饲养员在t_i-d_{h_i}时刻以后出发就可以接到它；

注意，饲养员可以在负时刻就出发！！！我之前想多了以为只能在非负时刻出发而纳闷了好半天

我们设t_i-d_{h_i}为新的t_i，然后将所有的t_i排序。

然后开始DP：

设f[i][j]表示：前i只猫，派出j个人，的最优时间。再设s_i表示t_i的前缀和。

则有f[i][j]=\min\limits_{k=0}^{i-1}\{f[k][j-1]+t_i*(i-k)-(s_i-s_k)\}

我们这样就可以写出O(m^2p)的代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p,d[100100],t[100100],s[100100],f[100100][110],qwq=0x3f3f3f3f3f3f3f3f;
signed main(){
    scanf("%lld%lld%lld",&n,&m,&p),memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=2;i<=n;i++)scanf("%lld",&d[i]),d[i]+=d[i-1];
//  for(int i=1;i<=n;i++)printf("%lld ",d[i]);puts("");
    for(int i=1,x,y;i<=m;i++)scanf("%lld%lld",&x,&y),t[i]=y-d[x];
//  printf("%lld\n",res);
//  for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
    sort(t+1,t+m+1);
    for(int i=1;i<=m;i++)s[i]=s[i-1]+t[i];
//  for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
    f[0][0]=0;
    for(int j=1;j<=p;j++)for(int i=1;i<=m;i++)for(int k=0;k<i;k++)f[i][j]=min(f[i][j],f[k][j-1]+(i-k)*t[i]-(s[i]-s[k]));
    for(int i=1;i<=p;i++)qwq=min(qwq,f[m][i]);
    printf("%lld\n",qwq);
    return 0;
}

然后考虑斜率优化一下：

在f[i][j]中，我们按照列优先（先枚举j）的顺序进行DP；并且，设f[i][j-1]为F[i]。

设j<k<i（不是同一个j）。则如果j比k优，则有：

拆开

抵消

移项

除过去（注意j-k是负数）

右边的t_i是递增的（排过序了），因此可以采用单调队列维护斜率；然后维护一个下凸壳即可。复杂度O(mp)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p,d[100100],t[100100],s[100100],f[100100][110],qwq=0x3f3f3f3f3f3f3f3f,l,r,q[100100];
signed main(){
    scanf("%lld%lld%lld",&n,&m,&p),memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=2;i<=n;i++)scanf("%lld",&d[i]),d[i]+=d[i-1];
//  for(int i=1;i<=n;i++)printf("%lld ",d[i]);puts("");
    for(int i=1,x,y;i<=m;i++)scanf("%lld%lld",&x,&y),t[i]=y-d[x];
//  printf("%lld\n",res);
//  for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
    sort(t+1,t+m+1);
    for(int i=1;i<=m;i++)s[i]=s[i-1]+t[i];
//  for(int i=1;i<=m;i++)printf("%lld ",t[i]);puts("");
    f[0][0]=0;
    for(int j=1;j<=p;j++){
        l=r=0;
        for(int i=1;i<=m;i++){
            while(r-l&&(f[q[l]][j-1]-f[q[l+1]][j-1]+s[q[l]]-s[q[l+1]])>=(q[l]-q[l+1])*t[i])l++;
            f[i][j]=f[q[l]][j-1]+(i-q[l])*t[i]-(s[i]-s[q[l]]);
            while(r-l&&(f[q[r-1]][j-1]-f[q[r]][j-1]+s[q[r-1]]-s[q[r]])*(q[r]-i)>=(f[q[r]][j-1]-f[i][j-1]+s[q[r]]-s[i])*(q[r-1]-q[r]))r--;
            q[++r]=i;
        }
    }
    for(int i=1;i<=p;i++)qwq=min(qwq,f[m][i]);
    printf("%lld\n",qwq);
    return 0;
}

XVIII.[HAOI2010]软件安装

不知道大家有没有做过这道题[CTSC1997]选课啊，反正我一看到这道题，就想起了它——都是树上背包。所以我便高高兴兴的敲了一发背包交上去。

然后呢？光荣的WA掉了。

为什么呢？

因为这道题和选课不一样；选课是你没有修完前一节课就不能修这节；但是本题是你装软件是可以随便装，想咋装就咋装的——只不过会不会起效就不知道了。因此，如果成环的话，只要整个环全装上就行了。

那么我们就SCC缩个点，在缩出来的树上背包一下就行了（实际上数据还可以加强成DAG的……）

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,w[110],v[110],f[110][510],g[510],res,col[110],val[110],sz[110],in[110],c;
namespace SCC{
    int tot,dfn[310],low[310],head[310],cnt;
    struct node{
        int to,next;
    }edge[200100];
    void ae(int u,int v){
    //  cout<<u<<" "<<v<<endl;
        edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    }
    stack<int>stk;
    void Tarjan(int x){
        dfn[x]=low[x]=++tot,stk.push(x);
        for(int i=head[x];i!=-1;i=edge[i].next){
            if(!dfn[edge[i].to])Tarjan(edge[i].to),low[x]=min(low[x],low[edge[i].to]);
            if(!col[edge[i].to])low[x]=min(low[x],dfn[edge[i].to]);
        }
        if(low[x]<dfn[x])return;
        c++;
        while(stk.top()!=x)col[stk.top()]=c,val[c]+=v[stk.top()],sz[c]+=w[stk.top()],stk.pop();
        col[stk.top()]=c,val[c]+=v[stk.top()],sz[c]+=w[stk.top()],stk.pop();
    }
}
namespace DP{
    int head[110],cnt;
    struct node{
        int to,next;
    }edge[110];
    void ae(int u,int v){
//      printf("%d %d\n",u,v);
        edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    }
    void dfs(int x){
        if(sz[x]<=m)f[x][sz[x]]=val[x];
        for(int i=head[x];i!=-1;i=edge[i].next){
            dfs(edge[i].to);
            for(int j=0;j<=m;j++)g[j]=f[x][j];
            for(int j=0;j<=m;j++)for(int k=0;j+k<=m;k++)if(f[x][j]!=-1&&f[edge[i].to][k]!=-1)g[j+k]=max(g[j+k],f[x][j]+f[edge[i].to][k]);
            for(int j=0;j<=m;j++)f[x][j]=g[j];
        }
    }   
}
int main(){
    scanf("%d%d",&n,&m),memset(f,-1,sizeof(f)),memset(SCC::head,-1,sizeof(SCC::head)),memset(DP::head,-1,sizeof(DP::head));
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x)SCC::ae(x,i);
    }
    for(int i=1;i<=n;i++)if(!SCC::dfn[i])SCC::Tarjan(i);
//  for(int i=1;i<=c;i++)printf("%d %d\n",val[i],sz[i]);
    for(int i=1;i<=n;i++)for(int j=SCC::head[i];j!=-1;j=SCC::edge[j].next)if(col[i]!=col[SCC::edge[j].to])DP::ae(col[i],col[SCC::edge[j].to]),in[col[SCC::edge[j].to]]++;
    for(int i=1;i<=c;i++)if(!in[i])DP::ae(0,i);
    DP::dfs(0);
    for(int i=0;i<=m;i++)res=max(res,f[0][i]);
    printf("%d\n",res);
    return 0;
}

IXX.[HNOI2005]星际贸易

第一问直接背包一下就行，是模板。

然后，因为题面中的一句话：

……并使得只有一种获得最大贸易值的方法。

因此我们可以直接根据各状态是从哪个前驱状态转移而来直接得出那些必须要访问的星球。

注意，你所规定的这条路径必须满足贸易值最大（不管合不合法（走不走的完），但贸易值必须最大），不然你就会像我一样死活看不懂第二组样例……

我们考虑DP。

设f[i][j]表示：当前在位置i，已经进行了所有的操作随时可以起飞，并且当前舰上还有j份燃料的最小代价。

思路1.暴力DP：

我们有

其中，p[i]是i星球一份暗物质的费用，fx[i]是i位置修船的费用。

复杂度O(n^4)，可以拿到55\%。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,l,a[2010],b[2010],dis[2010],p[2010],fx[2010],f[2010][4010],mp,mn=0x3f3f3f3f;
bool cho[2010];
int main(){
    scanf("%d%d%d%d",&n,&m,&r,&l),memset(f,0x80,sizeof(f)),r=min(r,2*n);
    if(r<2){puts("Poor Coke!");return 0;}
    for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&a[i],&b[i],&dis[i],&p[i],&fx[i]);
    for(int i=1;i<=n;i++)if(dis[i]-dis[i-1]>l){puts("Poor Coke!");return 0;}
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<a[i];j++)f[i][j]=f[i-1][j];
        for(int j=a[i];j<=m;j++)f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
    }
    for(int i=0;i<=m;i++)if(f[n][mp]<f[n][i])mp=i;
    for(int i=n,j=mp;i;i--){
        if(f[i][j]==f[i-1][j])continue;
        cho[i]=true,j-=a[i];
    }
//  for(int i=1;i<=n;i++)printf("%d ",cho[i]);puts("");
    mp=f[n][mp];
    memset(f,0x3f,sizeof(f));
    f[0][r]=0;
    for(int i=1;i<=n;i++)for(int j=0;j<=r;j++){
        for(int k=i-1;k>=0;k--){
            if(dis[i]-dis[k]>l)break;
            if(!p[i]){
                if(j>=2)f[i][j]=min(f[i][j],f[k][j+2]+fx[i]);
                else f[i][j]=0x3f3f3f3f;
            }
            else for(int l=2;l<=min(j+2,r);l++)f[i][j]=min(f[i][j],f[k][l]+(j-l+2)*p[i]+fx[i]);
            if(cho[k])break;
        }
//      printf("%d %d:%d\n",i,j,f[i][j]);
    }
    for(int i=0;i<=r;i++)mn=min(mn,f[n][i]);
    if(mn==0x3f3f3f3f){puts("Poor Coke!");return 0;}
    printf("%d %d\n",mp,mp-mn);
    return 0;
} 

思路2.背包

因为在位置i买暗物质的操作实际上就是一个完全背包的效果，所以我们完全可以不枚举l，转而采用完全背包的形式在O(n^3)解决它。可以拿到65\%。

即：f[i][j]=\min(f[k][j+2]+f[i],f[i][j-1]+p[i])。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,l,a[2010],b[2010],dis[2010],p[2010],fx[2010],f[2010][4010],mp,mn=0x3f3f3f3f;
bool cho[2010];
int main(){
    scanf("%d%d%d%d",&n,&m,&r,&l),memset(f,0x80,sizeof(f)),r=min(r,2*n);
    if(r<2){puts("Poor Coke!");return 0;}
    for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&a[i],&b[i],&dis[i],&p[i],&fx[i]);
    for(int i=1;i<=n;i++)if(dis[i]-dis[i-1]>l){puts("Poor Coke!");return 0;}
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<a[i];j++)f[i][j]=f[i-1][j];
        for(int j=a[i];j<=m;j++)f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
    }
    for(int i=0;i<=m;i++)if(f[n][mp]<f[n][i])mp=i;
    for(int i=n,j=mp;i;i--){
        if(f[i][j]==f[i-1][j])continue;
        cho[i]=true,j-=a[i];
    }
//  for(int i=1;i<=n;i++)printf("%d ",cho[i]);puts("");
    mp=f[n][mp];
    memset(f,0x3f,sizeof(f));
    f[0][r]=0;
    for(int i=1;i<=n;i++)for(int j=0;j<=r;j++){
        for(int k=i-1;k>=0;k--){
            if(dis[i]-dis[k]>l)break;
            f[i][j]=min(f[i][j],f[k][j+2]+fx[i]);
            if(cho[k])break;
        }
        if(p[i]&&j)f[i][j]=min(f[i][j],f[i][j-1]+p[i]);
//      printf("%d %d:%d\n",i,j,f[i][j]);
    }
    for(int i=0;i<=r;i++)mn=min(mn,f[n][i]);
    if(mn==0x3f3f3f3f){puts("Poor Coke!");return 0;}
    printf("%d %d\n",mp,mp-mn);
    return 0;
} 

思路3.单调队列

因为f[k][j+2]这个东西随着i的增加，每个i都要枚举一下，因此可以采用单调队列来保存每个暗物质数量j可以转移的最优位置，并且按照距离及时弹出已经距离i太远的位置。复杂度O(n^2)，期望得分100\%。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,l,a[2010],b[2010],dis[2010],p[2010],fx[2010],f[2010][4010],mp,mn=0x3f3f3f3f;
deque<int>q[2010];
bool cho[2010];
int main(){
    scanf("%d%d%d%d",&n,&m,&r,&l),memset(f,0x80,sizeof(f)),r=min(r,2*n);
    if(r<2){puts("Poor Coke!");return 0;}
    for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&a[i],&b[i],&dis[i],&p[i],&fx[i]);
    for(int i=1;i<=n;i++)if(dis[i]-dis[i-1]>l){puts("Poor Coke!");return 0;}
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<a[i];j++)f[i][j]=f[i-1][j];
        for(int j=a[i];j<=m;j++)f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
    }
    for(int i=0;i<=m;i++)if(f[n][mp]<f[n][i])mp=i;
    for(int i=n,j=mp;i;i--){
        if(f[i][j]==f[i-1][j])continue;
        cho[i]=true,j-=a[i];
    }
//  for(int i=1;i<=n;i++)printf("%d ",cho[i]);puts("");
    mp=f[n][mp];
    memset(f,0x3f,sizeof(f));
    f[0][r]=0;
    for(int i=1;i<=n;i++)for(int j=0;j<=r;j++){
        while(!q[j+2].empty()&&dis[i]-dis[q[j+2].front()]>l)q[j+2].pop_front();
        while(!q[j+2].empty()&&f[q[j+2].back()][j+2]>=f[i-1][j+2])q[j+2].pop_back();
        q[j+2].push_back(i-1);
        f[i][j]=min(f[i][j],f[q[j+2].front()][j+2]+fx[i]);
        if(p[i]&&j)f[i][j]=min(f[i][j],f[i][j-1]+p[i]);
        if(cho[i])q[j+2].clear();
//      printf("%d %d:%d\n",i,j,f[i][j]);
    }
    for(int i=0;i<=r;i++)mn=min(mn,f[n][i]);
    if(mn==0x3f3f3f3f){puts("Poor Coke!");return 0;}
    printf("%d %d\n",mp,mp-mn);
    return 0;
} 

XX.[SCOI2010]股票交易

这题状态很好想：设f[i][j]表示：第i天，持有j支股票，的最大收益。

然后我就脑残了，想了个O(n^2m^2)的弱智初始DP，然后就WA掉惹。

实际上转移也挺简单的。设第i天买股票花a_i元，卖股票花b_i元，可以买A_i次，卖B_i次。

1. 从起始状态转移。即，如果有j\leq A_i，f[i][j]=-j*a_i。

2. 这一时刻不买。即，f[i][j]=f[i-1][j]。

3. 从i-w-1时刻买。即，f[i][j]=\max\{f[i-w-1][l]+\text{买或卖的费用}\}

然后1和2都是nm的；3套上单调队列也是nm的；总复杂度O(nm)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,w,a[2010],b[2010],A[2010],B[2010];
ll f[2010][2010];
deque<int>q;
int main(){
    scanf("%d%d%d",&n,&m,&w),w++,memset(f,0x80,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i],&b[i],&A[i],&B[i]);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(j<=A[i])f[i][j]=-j*a[i];
            f[i][j]=max(f[i][j],f[i-1][j]); 
        }
        if(i-w<=0)continue;
        int k=i-w;
        q.clear();
        for(int j=0;j<=m;j++){
            while(!q.empty()&&j-q.front()>A[i])q.pop_front();
            while(!q.empty()&&f[k][q.back()]-(j-q.back())*a[i]<=f[k][j])q.pop_back();
            q.push_back(j);
            f[i][j]=max(f[i][j],f[k][q.front()]-(j-q.front())*a[i]);
        }
        q.clear();
        for(int j=m;j>=0;j--){
            while(!q.empty()&&q.front()-j>B[i])q.pop_front();
            while(!q.empty()&&f[k][q.back()]+(q.back()-j)*b[i]<=f[k][j])q.pop_back();
            q.push_back(j);
            f[i][j]=max(f[i][j],f[k][q.front()]+(q.front()-j)*b[i]);
        }
    }
//  for(int i=1;i<=n;i++){for(int j=0;j<=m;j++)printf("%d ",f[i][j]);puts("");}
    printf("%lld\n",f[n][0]);
    return 0;
}

XXI.[HAOI2011]Problem c

这题还是挺简单的~~~

关于每个位置i，在一种合法的方案 a 中，必有

因为这个可以看作是把所有x的儿子所代表的拓扑序列归并到一起，所以直接C一下找出要填的位置即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1001000],sz[1001000],fac[1001000],inv[1001000];
int ksm(int x,int y){
    int z=1;
    for(;y;x=(1ll*x*x)%m,y>>=1)if(y&1)z=(1ll*z*x)%m;
    return z;
}
int C(int x,int y){
    return 1ll*fac[x]*inv[y]%m*inv[x-y]%m;
}
int main(){
    scanf("%d%d",&n,&m),fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=(1ll*fac[i-1]*i)%m;
    inv[n]=ksm(fac[n],m-2);
    for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%m;
    for(int i=1;i<=n;i++)f[i]=1;
    for(int i=n;i>1;i--){
        sz[i]++;
        f[i>>1]=(1ll*f[i>>1]*C(sz[i>>1]+sz[i],sz[i])%m*f[i])%m;
        sz[i>>1]+=sz[i];
    } 
    printf("%d\n",f[1]);
    return 0;
}

XXIII.[HNOI2010]公交线路

状压+矩乘的好题。

因为每p个位置中，每辆车就至少有1个位置，

所以我们可以状压一下。

设f[i][j]表示：

区间[i,i+p-1]内的车站现在的规划情况是j的方案数。

显然，必有j的第p位是1，且j共有k位是1（j的第p位对应着i）。

则f[i][j]=\sum f[i-1][k]，其中k能转移到j。

那什么样的k能转移到j呢？

我们将k左移一位（即增加了 i+p-1 一位），然后删去第p位的数（即删去第 i-1 位），得到了一个k'。

如果k'和j只相差恰好1位，那么k就可以转移到j（第i-1位的车刚好跑到了着相差的一位）。

然后发现，对于每个f[i][j]，它的祖先的k都是完全一致的；因此可以矩乘优化，建立转移矩阵T[k][j]，如果状态k可以转移到j，则T[k][j]=1，否则为0。

则复杂度为S^3\log n，其中S是合法状态数量（即符合j的第p位是1，且j共有k位是1的j的数量）。我们有S=C_{p-1}^{k-1}，当p=10,k=5\ \operatorname{or}\ 6时取得最大值，有S=C_9^4\ \operatorname{or}\ C_9^5=126。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=30031;
int n,m,p,len,sta[150];
struct mat{
    int g[150][150];
    mat(){memset(g,0,sizeof(g));}
    friend mat operator *(const mat &x,const mat &y){
        mat z;
        for(int i=0;i<len;i++)for(int j=0;j<len;j++)for(int k=0;k<len;k++)(z.g[i][j]+=x.g[i][k]*y.g[k][j])%=mod;
        return z;
    }
}X,I;
bool che(int x,int y){
    x<<=1,x-=(1<<p);
    return __builtin_popcount(x^y)<=1;
}
void ksm(int y){
    for(;y;X=X*X,y>>=1)if(y&1)I=I*X;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=(1<<(p-1));i<(1<<p);i++)if(__builtin_popcount(i)==m)sta[len++]=i;
    for(int i=0;i<len;i++)I.g[i][i]=1;
    for(int i=0;i<len;i++)for(int j=0;j<len;j++)X.g[i][j]=che(sta[i],sta[j]);
    ksm(n-m);
    printf("%d\n",I.g[len-1][len-1]);
    return 0;
} 

XXIV.[HEOI2013]SAO

这题思路和我们之前的XXII.[ZJOI2010]排列计数类似，也是一棵树的拓扑序数。但是，那题边只有一种情况（相当于这题的第三组20\%的特殊限制），这题情况就比较复杂。

我们先忽略边方向的限制，把整张图看作一棵无向树。不妨令0号节点为根。

发现只维护一维信息并不能准确地合并状态。此题的数据访问暗示我们采用n^2算法，因此考虑二维DP。

设f[i][j]表示：在以i为根的子树中，i的拓扑序为j的方案数。则答案为\sum f[0][i]。

我们考虑将x同它的某个儿子y合并。设它们的当前大小分别为sz_x和sz_y。

假设我们现在要合并f[x][i]和f[y][j](i\leq sz_x,j\leq sz_y)。我们枚举一个k，表示最终合并后，有k个位于y子树内的点排在了x前面。

这时，必有k\geq j，因为那k个排在y前面的点都必定放在x前面。

则这次枚举贡献给了f[x][i+k]。

那么具体贡献了多少呢？

首先一定有f[x][i]和f[y][j]。

然后，前i+k-1个位置中，有k个位置是来自y的，有C_{i+k-1}^k。

后sz_x+sz_y-i-k个位置中，有sz_x-i个位置是来自x的，有C_{sz_x+sz_y-i-k}^{sz_x-i}。

然后最后的贡献就是这四个东西的乘积。

唯一有区别的是k的枚举范围变成k<j。

复杂度O(n^3)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int T,n,f[1010][1010],head[1010],cnt,sz[1010],C[1010][1010],res,g[1010];
struct node{
    int to,next,val;
}edge[2010];
void ae(int u,int v,int w){
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val= w,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=-w,head[v]=cnt++;
}
void dfs(int x,int fa){
    sz[x]=1,f[x][1]=1;
    for(int e=head[x],y;e!=-1;e=edge[e].next){
        if((y=edge[e].to)==fa)continue;
        dfs(y,x);
        for(int i=1;i<=sz[x]+sz[y];i++)g[i]=0;
        if(edge[e].val==-1)for(int i=1;i<=sz[x];i++)for(int j=1;j<=sz[y];j++)for(int k=j;k<=sz[y];k++)g[i+k]=(1ll*f[y][j]*C[i+k-1][k]%mod*f[x][i]%mod*C[sz[x]+sz[y]-i-k][sz[x]-i]%mod+g[i+k])%mod;
        if(edge[e].val== 1)for(int i=1;i<=sz[x];i++)for(int j=1;j<=sz[y];j++)for(int k=0;k<     j;k++)g[i+k]=(1ll*f[y][j]*C[i+k-1][k]%mod*f[x][i]%mod*C[sz[x]+sz[y]-i-k][sz[x]-i]%mod+g[i+k])%mod;
        for(int i=1;i<=sz[x]+sz[y];i++)f[x][i]=g[i];
        sz[x]+=sz[y];
    }
}
int gt(){
    char c=getchar();
    while(c!='>'&&c!='<')c=getchar();
    return c=='>'?1:-1;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n),memset(head,-1,sizeof(head)),memset(f,0,sizeof(f)),cnt=0;
        for(int i=0;i<=n;i++)C[i][0]=1;
        for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        for(int i=1;i<n;i++){
            int x,y,z;
            scanf("%d",&x);
            z=gt();
            scanf("%d",&y);
            ae(x,y,z);
        }
        dfs(0,-1),res=0;
        for(int i=1;i<=n;i++)(res+=f[0][i])%=mod;
        printf("%d\n",res);
    }
    return 0;
}

考虑优化。

我们看到这四个东西：

发现，只有f[y][j]一个是与j有关的！

于是，我们可以改变枚举顺序，枚举k，然后直接用f[y]的前缀和就可以了。

因为少了一重循环，复杂度O(n^2)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int T,n,f[1010][1010],head[1010],cnt,sz[1010],C[1010][1010],res,g[1010],s[1010][1010];
struct node{
    int to,next,val;
}edge[2010];
void ae(int u,int v,int w){
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val= w,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=-w,head[v]=cnt++;
}
void dfs(int x,int fa){
    sz[x]=1,f[x][1]=1;
    for(int e=head[x],y;e!=-1;e=edge[e].next){
        if((y=edge[e].to)==fa)continue;
        dfs(y,x);
        for(int i=1;i<=sz[x]+sz[y];i++)g[i]=0;
        if(edge[e].val==-1)for(int i=1;i<=sz[x];i++)for(int k=1;k<=sz[y];k++)g[i+k]=(1ll*s[y][k]*C[i+k-1][k]%mod*f[x][i]%mod*C[sz[x]+sz[y]-i-k][sz[x]-i]%mod+g[i+k])%mod;
        if(edge[e].val== 1)for(int i=1;i<=sz[x];i++)for(int k=0;k<=sz[y];k++)g[i+k]=(1ll*(s[y][sz[y]]-s[y][k]+mod)%mod*C[i+k-1][k]%mod*f[x][i]%mod*C[sz[x]+sz[y]-i-k][sz[x]-i]%mod+g[i+k])%mod;
        for(int i=1;i<=sz[x]+sz[y];i++)f[x][i]=g[i];
        sz[x]+=sz[y];
    }
    for(int i=1;i<=sz[x];i++)s[x][i]=(s[x][i-1]+f[x][i])%mod;
}
int gt(){
    char c=getchar();
    while(c!='>'&&c!='<')c=getchar();
    return c=='>'?1:-1;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n),memset(head,-1,sizeof(head)),memset(f,0,sizeof(f)),cnt=0;
        for(int i=0;i<=n;i++)C[i][0]=1;
        for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
        for(int i=1;i<n;i++){
            int x,y,z;
            scanf("%d",&x);
            z=gt();
            scanf("%d",&y);
            ae(x,y,z);
        }
        dfs(0,-1),res=0;
        for(int i=1;i<=n;i++)(res+=f[0][i])%=mod;
        printf("%d\n",res);
    }
    return 0;
}

XXV.[CQOI2017]老C的键盘

和前一题 完 全 一 致。

那就不讲了，双倍经验水过。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,f[1010][1010],head[1010],cnt,sz[1010],C[1010][1010],res,g[1010],s[1010][1010];
struct node{
    int to,next,val;
}edge[2010];
void ae(int u,int v,int w){
//  printf("%d %d %d\n",u,v,w);
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
}
void dfs(int x){
    sz[x]=1,f[x][1]=1;
    for(int e=head[x],y;e!=-1;e=edge[e].next){
        y=edge[e].to;
        dfs(y);
        for(int i=1;i<=sz[x]+sz[y];i++)g[i]=0;
        if(edge[e].val==-1)for(int i=1;i<=sz[x];i++)for(int k=1;k<=sz[y];k++)g[i+k]=(1ll*s[y][k]*C[i+k-1][k]%mod*f[x][i]%mod*C[sz[x]+sz[y]-i-k][sz[x]-i]%mod+g[i+k])%mod;
        if(edge[e].val== 1)for(int i=1;i<=sz[x];i++)for(int k=0;k<=sz[y];k++)g[i+k]=(1ll*(s[y][sz[y]]-s[y][k]+mod)%mod*C[i+k-1][k]%mod*f[x][i]%mod*C[sz[x]+sz[y]-i-k][sz[x]-i]%mod+g[i+k])%mod;
        for(int i=1;i<=sz[x]+sz[y];i++)f[x][i]=g[i];
        sz[x]+=sz[y];
    }
    for(int i=1;i<=sz[x];i++)s[x][i]=(s[x][i-1]+f[x][i])%mod;
}
char str[1010];
int main(){
    scanf("%d",&n),memset(head,-1,sizeof(head));
    for(int i=0;i<=n;i++)C[i][0]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    scanf("%s",str+2);
    for(int i=2;i<=n;i++)ae(i>>1,i,str[i]=='>'?1:-1);
    dfs(1);
    for(int i=1;i<=n;i++)(res+=f[1][i])%=mod;
    printf("%d\n",res);
    return 0;
}

XXVI.[FJOI2007]轮状病毒

论此题的一百种不同解法

首先，这题是有通项公式的——

我们让f[i]中后j个数单独分一组，则剩下的是f[i-j]；这j个数选出一个点，j种选法。

现在我们强制1和n在一起；

方案数为

我们选出i个节点放在两边，共有i-1种放法；

从中选出一个连到中间，共有i种选法；

剩下的部分是f[n-i]。

然后答案即为num+f[n]。

加上高精度，复杂度O(n^3)。

另外这个f是可以通过差分达到线性递推的（当然加上高精度还是O(n^2)）。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
struct Wint:vector<int>{
    Wint(int n=0)
    {
        push_back(n);
        check();
    }
    Wint& check(){
        while(!empty()&&!back())pop_back();
        if(empty())return *this;
        for(int i=1; i<size(); ++i)(*this)[i]+=(*this)[i-1]/10,(*this)[i-1]%=10;
        while(back()>=10)push_back(back()/10),(*this)[size()-2]%=10;
        return *this;
    }
}f[110],res;
Wint& operator+=(Wint &a,const Wint &b){
    if(a.size()<b.size())a.resize(b.size());
    for(int i=0; i!=b.size(); ++i)a[i]+=b[i];
    return a.check();
}
Wint operator+(Wint a,const Wint &b){
    return a+=b;
}
Wint& operator*=(Wint &a,const int &b){
    for(int i=0;i<a.size();i++)a[i]*=b;
    return a.check();
}
Wint operator*(Wint a,const int &b){
    return a*=b;
}
void print(Wint a){
    for(int i=a.size()-1;i>=0;i--)putchar(a[i]+'0');
}
int main(){
    scanf("%d",&n);
    f[0]=Wint(1),f[1]=Wint(1);
    for(int i=2;i<=n;i++)for(int j=1;j<=i;j++)f[i]+=f[i-j]*j;
    res=f[n];
    for(int i=2;i<=n;i++)res+=f[n-i]*(i*(i-1));
    print(res);
    return 0;
}

XXVII.[SHOI2012]随机树

化简就得到了

释义：我们枚举左子树中放进去k个子节点。则左/右节点至少有一个深度\geq j-1的状态都是合法的。但是，左右节点深度都\geq j-1的情况在两个中都被算进去了；因此需要减去这种可能。

这个分母上的?，就是出现这种左右子树size分配的可能性。

考虑这种可能性的大小。

我们设g_i表示构成一棵有i个叶节点的树的方案数。则有g_i=(i-1)!，因为每“扩展”一个点就相当于从i个叶子中选了一个叶子出来，有i种选法；则有g_i=\prod\limits_{j=1}^{i-1}j=(i-1)!。

显然，这种可能性应该等于g_{k}*g_{i-k}*?（这个?是一个新的?）。我们将两棵子树合并，首先两棵子树自己内部扩展的顺序已经被g决定了；但是合并的顺序可是可以随便指定的；合并顺序的种数等于C_{i-2}^{k-1}，因为i个叶节点就意味着i-2次合并（当前节点自己本身就占用一次合并），这i-2次合并选出k-1次合并在左子树上。

则可能性的大小为g_{k}*g_{i-k}*C_{i-2}^{k-1}=(k-1)!*(i-k-1)!*\dfrac{(i-2)!}{(k-1)!*(i-2-k+1)!}=(i-2)!

然后分母上的?就是\dfrac{g_i}{(i-2)!}=\dfrac{(i-1)!}{(i-2)!}=(i-1)。

于是我们现在有

有一个式子：

其中E(x)表示x的期望，P(i)表示i\leq x的概率。

证明：

设p(i)表示i=x的概率，P(i)表示i\leq x的概率，

则E(x)=\sum\limits_{i=1}^{\infty}p(i)*i

而P(i)=\sum\limits_{j=i}^{\infty}p(j)

则

证毕。

依据此式，则答案为\sum\limits_{i=1}^{n-1}f[n][i]。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
namespace T1{
    double f[110];
    double work(){
        f[1]=0;
        for(int i=2;i<=n;i++)f[i]=f[i-1]+2.0/i;
        return f[n];
    }
}
namespace T2{
    double f[110][110];
    double work(){
        for(int i=1;i<=n;i++)f[i][0]=1;
        for(int i=2;i<=n;i++)for(int j=1;j<i;j++){
            for(int k=1;k<i;k++)f[i][j]+=f[i-k][j-1]+f[k][j-1]-f[i-k][j-1]*f[k][j-1];
            f[i][j]/=i-1;
        }
        double res=0;
        for(int i=1;i<n;i++)res+=f[n][i];
        return res;
    }
} 
int main(){
    scanf("%d%d",&m,&n);
    if(m==1)printf("%lf\n",T1::work());
    if(m==2)printf("%lf\n",T2::work());
    return 0;
}

XXVIII.[HAOI2006]数字序列

第一问：

正难则反。我们考虑从这个序列中找出最多可以保留的数。

如果两个下标i,j(i<j)都是要保留的，那么保留的充要条件就是

因为(i,j)开区间中的其它数要保证仍然有可以修改到的位置。例如 10 4 3 12 这组数据中，10和12便不能同时选择，因为4和3要有修改的位置。

上面式子调换一下，便是

设a_i-i=b_i，则

则一组合法的修改结果肯定是一个“台阶”形。

我们发现，对于一段“台阶”：

如果它向下的箭头比向上的箭头要多，那么台阶上移一定不会更劣。反之亦然。

比如上图最左端那级台阶，就是上移下移都可以；中间的台阶，向上移更优；右面的台阶，向下移最好。

这样我们就可以构思出一种移台阶的方法：

对于一段台阶，如果它向上最好，则一直向上移直到和右边的下一段台阶齐平。然后合并两段台阶，再对新生成的这段台阶进行类似的操作。这种操作一定不会使答案变差。

则全部移完后，我们发现原本一小段一小段的台阶，要么同左边合并了，要么同右边合并了，反正最后一定是左边与左端点有一段台阶，右边与右端点有一段台阶。我们可以枚举左右台阶间的断点取\min。

这样我们就可以DP了。设f_i表示以i结尾的LIS的长度，g_i表示将[1,i]中所有台阶全都移完，且i是某条LIS中的一个位置时的最小代价。显然，g_i能从所有j<i,b_j<b_i,f_j=f_i-1的j转移过来。如果令b_0=-\infty,b_{n+1}=+\infty,f_0=0,f_{n+1}=\max\limits_{i=1}^{n}\{f_i\}+1的话，则答案为g_{n+1}。

在极端数据下，这种暴力转移复杂度是O(n^3)的（枚举i是O(n)的，枚举j在极端数据下是O(n)的，枚举断点也是O(n)的）。但是，“数据随机”让这个算法的期望复杂度优化成了O(n\log^2n)，轻松通过。

代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=1e6;
int n,a[50100],b[50100],f[50100],t[50100],lim,mx,g[50100],pre[50100],suf[50100];
vector<int>v;
void add(int x,int val){
    while(x<=lim)t[x]=max(t[x],val),x+=x&-x;
}
int ask(int x){
    int qwq=0;
    while(x)qwq=max(qwq,t[x]),x-=x&-x;
    return qwq;
}
vector<int>q[50100];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)b[i]=a[i]-i,v.push_back(b[i]);
    sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
    for(int i=1;i<=n;i++)b[i]=lower_bound(v.begin(),v.end(),b[i])-v.begin()+1;
    for(int i=1;i<=n;i++)f[i]=ask(b[i])+1,add(b[i],f[i]),mx=max(mx,f[i]);
    for(int i=1;i<=n;i++)b[i]=a[i]-i;
    printf("%d\n",n-mx);
    q[0].push_back(0);
    memset(g,0x3f3f3f3f,sizeof(g));
    b[0]=-INF;
    b[n+1]=INF;
    g[0]=0;
    f[n+1]=mx+1;
    for(int i=1;i<=n+1;i++){
        q[f[i]].push_back(i);
        for(auto j:q[f[i]-1]){
            if(b[j]>b[i])continue;
//          printf("%d %d:\n",j,i);
            pre[j]=suf[i]=0;
            for(int k=j+1;k<i;k++)pre[k]=pre[k-1]+abs(b[k]-b[j]);
            for(int k=i-1;k>j;k--)suf[k]=suf[k+1]+abs(b[k]-b[i]);
//          for(int k=j;k<i;k++)printf("%d ",pre[k]);puts("");
//          for(int k=j+1;k<=i;k++)printf("%d ",suf[k]);puts("");
            for(int k=j;k<i;k++)g[i]=min(g[i],g[j]+pre[k]+suf[k+1]);
        }       
    }
//  for(int i=0;i<=n+1;i++)printf("%9d ",f[i]);puts("");
//  for(int i=0;i<=n+1;i++)printf("%9d ",b[i]);puts("");
//  for(int i=0;i<=n+1;i++)printf("%9d ",g[i]);puts("");
    printf("%d\n",g[n+1]);
    return 0;
} 

XXIX.[SDOI2008]Sue的小球

DP做多了，手感自然就出来了。

话说这题打着“小球”的名字题目中却是“彩蛋”是怎么回事

首先，这个下落速度v，尽管题面中说它可能为负数，但我们想一想，这可能吗？如果是负数答案就是正无穷（可以等着这个球一直向上飞），因此排除球速为负的可能。

如果是这样的话，那么，当我们经过一个球时，随手将它射爆明显是更好的行为。因此，无论何时，我们球已经被射下的位置一定是一个包含起始点x_0的区间。

我们将所有球按照位置在x_0左边还是右边压进两个vector中（下标从0开始）。在左边的vector（设为v1）中，我们按照x值从大到小排序并处理；在右边（设为v2），我们从小到大排序。同时，我们在v1和v2中都压入一个x=x_0的球，方便初始化。

我们设f[i][j][0/1]表示：当前进行到v1的第i位，v2的第j位，同时位于这个区间的左/右端点的情况。我们可以提前计算出所有小球初始y值的和，这样我们只需要最小化捡球过程中球下落的距离即可。

我们设s[i][j]表示：除了v1前i位和v2前j位外，其它球1s内下落的距离之和（这借鉴了XII.任务安排中费用提前计算的经典思想）。在实现中，这个可以直接通过前缀和做出。设x1[i]表示v1的x值，x2[j]表示v2的x值。

我们有

然后因为两边可以互相走，所以还有

两种转移取\min即可。

复杂度O(n^2)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,X,s1[1010],s2[1010],sy,f[1010][1010][2],sv;
struct node{
    int x,y,v;
    node(int a=0,int b=0,int c=0){x=a,y=b,v=c;}
}b[1010];
vector<node>v1,v2;
bool cmp1(const node &x,const node &y){
    return x.x<y.x;
}
bool cmp2(const node &x,const node &y){
    return x.x>y.x;
}
int main(){
    scanf("%d%d",&n,&X),memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1;i<=n;i++)scanf("%d",&b[i].x);
    for(int i=1;i<=n;i++)scanf("%d",&b[i].y),sy+=b[i].y;
    for(int i=1;i<=n;i++)scanf("%d",&b[i].v);
    for(int i=1;i<=n;i++){
        if(b[i].x<X)v1.push_back(b[i]);
        if(b[i].x>X)v2.push_back(b[i]);
    }
    v1.push_back(node(X,0,0)),v2.push_back(node(X,0,0));
    sort(v1.begin(),v1.end(),cmp2);
    sort(v2.begin(),v2.end(),cmp1);
    for(int i=1;i<v1.size();i++)s1[i]=s1[i-1]+v1[i].v;
    for(int i=1;i<v2.size();i++)s2[i]=s2[i-1]+v2[i].v;
//  for(int i=0;i<v1.size();i++)printf("%d %d %d\n",v1[i].x,v1[i].y,v1[i].v);puts("");
//  for(int i=0;i<v2.size();i++)printf("%d %d %d\n",v2[i].x,v2[i].y,v2[i].v);puts("");
    sv=s1[v1.size()-1]+s2[v2.size()-1];
    f[0][0][0]=f[0][0][1]=0;
    for(int i=0;i<v1.size();i++)for(int j=0;j<v2.size();j++){
        if(i)f[i][j][0]=f[i-1][j][0]+abs(v1[i].x-v1[i-1].x)*(sv-s1[i-1]-s2[j]);
        if(j)f[i][j][1]=f[i][j-1][1]+abs(v2[j].x-v2[j-1].x)*(sv-s1[i]-s2[j-1]);
        f[i][j][0]=min(f[i][j][0],f[i][j][1]+abs(v2[j].x-v1[i].x)*(sv-s1[i]-s2[j]));
        f[i][j][1]=min(f[i][j][1],f[i][j][0]+abs(v1[i].x-v2[j].x)*(sv-s1[i]-s2[j]));
    }
    double res=sy-min(f[v1.size()-1][v2.size()-1][0],f[v1.size()-1][v2.size()-1][1]);
    res/=1000;
    printf("%.3lf\n",res);
    return 0;
}

XXX.[SDOI2007]游戏

论STL的百种用法

可以观察到可以接龙的对构成一张DAG。因此我们要找到DAG中最长路。这个随便DP就可以了。

关键是找到可以互相转移的位置。

释义：

首先，答案是可以从前一位继承来的。

然后，因为对于每个i，选任何数量的v_k=p_i的k都是等价的，因此共有2^{s_i}-1中选法；

当i=j时，可以之前一个数也不选，就选i一个数，因此要加上1。

然后，因为\gcd具有结合律和交换律，所有\gcd(p_k,p_i)=p_j的状态也是可继承的。

则f[n][j]的状态是最终状态。

对于每个w_i，答案为\sum\limits_{v_j|w_i}f[n][j]。这个可以通过一个L^2的预处理求出g[i]=\sum\limits_{v_j|v_i}f[n][j]算出。

复杂度O(\sqrt{P}+L^2\log L+q)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,p,s[1001000],f[2][1001000],g[1001000],two[1001000];
vector<int>v; 
int main(){
    scanf("%d%d%d",&n,&m,&p);
    two[0]=1;
    for(int i=1;i<=n;i++)two[i]=(two[i-1]<<1)%mod;
    for(int i=0;i<=n;i++)two[i]=(two[i]-1+mod)%mod;
//  for(int i=0;i<=n;i++)printf("%d ",two[i]);puts("");
    for(int i=1;i*i<=p;i++){
        if(p%i)continue;
        v.push_back(i);
        if(i*i!=p)v.push_back(p/i);
    }
    sort(v.begin(),v.end());
//  for(auto i:v)printf("%d ",i);puts("");
    for(int i=1,x;i<=n;i++)scanf("%d",&x),x=__gcd(x,p),s[lower_bound(v.begin(),v.end(),x)-v.begin()]++;
//  for(int i=0;i<v.size();i++)printf("%d ",s[i]);puts("");puts("");
    for(int i=0;i<v.size();i++){
        for(int j=0;j<=i;j++)f[i&1][j]=0;
        f[i&1][i]=1;
        for(int j=0;j<i;j++){
            int gcd=__gcd(v[i],v[j]);
            gcd=lower_bound(v.begin(),v.end(),gcd)-v.begin();
            (f[i&1][gcd]+=f[!(i&1)][j])%=mod;
        }
        for(int j=0;j<=i;j++)f[i&1][j]=(1ll*f[i&1][j]*two[s[i]]+f[!(i&1)][j])%mod;
//      for(int j=0;j<=i;j++)printf("%d ",f[i&1][j]);puts("");
    }
    for(int i=0;i<v.size();i++)for(int j=0;j<=i;j++)if(!(v[i]%v[j]))(g[i]+=f[n&1][j])%=mod;
    for(int i=1,w;i<=m;i++)scanf("%d",&w),w=__gcd(w,p),printf("%d\n",g[lower_bound(v.begin(),v.end(),w)-v.begin()]);
    return 0;
} 

XXXIV.[SCOI2008]奖励关

每次将x的状态同y合并。

但这样就会出现一些问题——我们说要在j修个堡，但是这只是空头支票，没有算到k里面，当访问到j时，这个债是要还的！

因此对于f[x][x][k]，我们应该让k全体右移一位，即f[x][x][k]=f[x][x][k-1]，且f[x][x][0]=\infty（欠的一个堡还不回来，只能破产）。

还有，我们要计算x位置新产生的代价。这个代价要么x位置额外再修一个堡，要么就是到j的距离。因此我们有

则答案为f[0][0][K+1]（0号点有个免费的堡）。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,head[110],cnt,f[110][110][60],g[60],val[110],dis[110],anc[110],tp;
struct node{
    int to,next,val;
}edge[210];
void ae(int u,int v,int w){
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
}
void dfs(int x){
    anc[++tp]=x;
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        y=edge[i].to,dis[y]=dis[x]+edge[i].val,dfs(y);
        for(int j=1;j<=tp;j++){
            for(int k=0;k<=m;k++)g[k]=0x3f3f3f3f;
            for(int k=0;k<=m;k++)for(int l=0;l<=k;l++)g[k]=min(g[k],f[x][anc[j]][k-l]+f[y][anc[j]][l]);
            for(int k=0;k<=m;k++)f[x][anc[j]][k]=g[k];
        }
    }
    for(int j=m;j;j--)f[x][x][j]=f[x][x][j-1];
    f[x][x][0]=0x3f3f3f3f;
    for(int j=1;j<tp;j++)for(int k=0;k<=m;k++)f[x][anc[j]][k]+=val[x]*(dis[x]-dis[anc[j]]),f[x][anc[j]][k]=min(f[x][anc[j]][k],f[x][x][k]);
    tp--;
}
int main(){
    scanf("%d%d",&n,&m),m++,memset(head,-1,sizeof(head));
    for(int i=1,x,y;i<=n;i++)scanf("%d%d%d",&val[i],&x,&y),ae(x,i,y);
    dfs(0);
//  for(int i=1;i<=n;i++)printf("%d ",dis[i]*val[i]);puts("");
    printf("%d\n",f[0][0][m]);
    return 0;
}

XLI.CF1067A Array Without Local Maximums

这题DEBUG的我心态爆炸……后来发现是一个i打成j了……无语。

很容易想到，设f[i][j][0/1]表示：

到第i位时，位置i填入了j，且j\geq\text{位置i-1上的数}的状态是0/1的种数。

但这就会有问题：\geq反过来是\leq，而不是<。

因此我们还要记录一下是否相等。即设f[i][j][0/1/2]表示：

到第i位时，位置i填入了j，且j相较于上一位是小于/等于/大于。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int lim=200;
int n,num[100100],f[2][210][3],res;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
    if(num[1]==-1)for(int i=1;i<=lim;i++)f[1][i][0]=1;
    else f[1][num[1]][0]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=lim;j++)f[i&1][j][0]=f[i&1][j][1]=f[i&1][j][2]=0;
        int s;
        s=0;
        for(int j=1;j<=lim;j++){
            if(num[i]==-1||j==num[i])f[i&1][j][0]=s;
            (s+=f[!(i&1)][j][0]+f[!(i&1)][j][1]+f[!(i&1)][j][2])%=mod;
        }
        for(int j=1;j<=lim;j++)if(num[i]==-1||j==num[i])f[i&1][j][1]=(f[!(i&1)][j][0]+f[!(i&1)][j][1]+f[!(i&1)][j][2])%mod;
        s=0;
        for(int j=lim;j>=1;j--){
            if(num[i]==-1||j==num[i])f[i&1][j][2]=s;
            (s+=f[!(i&1)][j][1]+f[!(i&1)][j][2])%=mod;
        }
//      printf("%d:",i);for(int j=1;j<=lim;j++)if(f[i&1][j][0]||f[i&1][j][1])printf("(%d:%d %d)",j,f[i&1][j][0],f[i&1][j][1]);puts("");
    }
    for(int i=1;i<=lim;i++)(res+=f[n&1][i][1]+f[n&1][i][2])%=mod;
    printf("%lld\n",res);
    return 0;
}

XLII.CF1073E Segment Sum

数位DP裸题。

设f(pos,sta,lim,lead)表示：

到第pos个位置时，

但是这样会出问题：

要么可以找到一个点$k$，使得区间$[i,k-1]$与$[k+1,j]$之间没有边，并且$k$与两个集合连通。

并不表示这样的k唯一。例如，(1,2)\rightarrow(2,3)\rightarrow(3,4)中，2是一个k，3也是一个k，这同一种方案就被算了两边！

因此，我们可以只拿最左边那个k为准。即，i与k直接连边的k才是好k。

我们新增维数：

设f[i,j][0/1]表示：区间i,j全部连通，并且i,j强制连边/强制不连边。

则有

但是这个枚举会重复计算：假设x有两个儿子y_1和y_2，那么枚举y_1时，y_2的情况会被算上；同时，枚举y_2时，y_1也会被计算！

这样，我们必须只计算包含某个点pos的那种方案所贡献的答案。即，随便找出一个pos\in\{U\setminus x\}，则只有u\ni pos的u才是合法的u。

下面我们考虑加上边和LCA的限制，什么样的u才是合法的u。

I.LCA的限制

I.I.确保LCA是LCA而不是单纯的CA（common ancestor）。

即，对于(a_i,b_i,c_i)，如果有c_i=x，则a_i\in u与b_i \in u不能同时出现，否则它们的LCA就不是x了。

I.II.确保LCA一定是A（ancestor）

即，对于(a_i,b_i,c_i)，如果有c_i\in u，必有a_i\in u且b_i \in u。

II.边的限制

II.I.确保边的存在

即，对于(a_i,b_i)，如果有a_i\neq x且b_i\neq x但是a_i\in u与b_i\in u却有且只有一个条件成立，则这条边不可能存在。

II.II.确保边的可能

即，对于所有的y\ \operatorname{s.t.}\ \exists(x,y)，一个u里最多只能有这么一个y，因为一棵子树中最多只能同父亲连一条边。

如果只存在一个y\in u，那么转移就只能从这个y而来，即

否则，即不存在y\in u，就是上面的式子

边界为f[x][\{x\}]=1，最终答案为f[0][\{0\sim n-1\}]。

为了方便，采取记忆化搜索的形式实行。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p,f[15][1<<15];
bool g[15][15];
pair<int,int>e[15];
pair<pair<int,int>,int>l[110];
bool in(int x,int y){return x&(1<<y);}
int dfs(int x,int U){
    int &res=f[x][U],pos=0;
//  printf("%d,%d:%d\n",x,U,res);
    if(~res)return f[x][U];
    U^=(1<<x),res=0;
    for(;pos<n;pos++)if(in(U,pos))break;
    for(int u=U;u;u=(u-1)&U){
        if(!in(u,pos))continue;
        bool ok=true;
        for(int i=0;i<p;i++)if(l[i].second==x&&in(u,l[i].first.first)&&in(u,l[i].first.second)){ok=false;break;}
        if(!ok)continue;
        for(int i=0;i<p;i++)if(in(u,l[i].second)&&(!in(u,l[i].first.first)||!in(u,l[i].first.second))){ok=false;break;}
        if(!ok)continue;
        for(int i=0;i<m;i++)if(e[i].first!=x&&e[i].second!=x&&(in(u,e[i].first)^in(u,e[i].second))){ok=false;break;}
        if(!ok)continue;
        int cnt=0,y;
        for(int i=0;i<n;i++)if(g[x][i]&&in(u,i))cnt++,y=i;
        if(cnt>1)continue;
        if(cnt==1)res+=dfs(y,u)*dfs(x,U^u^(1<<x));
        else for(y=0;y<n;y++)if(in(u,y))res+=dfs(y,u)*dfs(x,U^u^(1<<x));
    }
//  printf("%d,%d:%d\n",x,U,res);
    return res;
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&p),memset(f,-1,sizeof(f));
    for(int i=0,x,y;i<m;i++)scanf("%lld%lld",&x,&y),x--,y--,g[x][y]=g[y][x]=true,e[i]=make_pair(x,y);
    for(int i=0,a,b,c;i<p;i++)scanf("%lld%lld%lld",&a,&b,&c),a--,b--,c--,l[i]=make_pair(make_pair(a,b),c);
    for(int i=0;i<n;i++)f[i][1<<i]=1;
    printf("%lld\n",dfs(0,(1<<n)-1));
    return 0;
} 

XLV.CF1088E Ehab and a component choosing problem

思路1.n^2DP。

考虑设f[i][j][0/1]表示：

节点i，子树分了j个集合，节点i是/否在某个集合内的最大值。

但是这样是没有前途的——你再怎么优化也优化不了，还是只能从题目本身的性质入手。

思路2.分析性质，O(n)解决。

发现，答案最大也不会超过最大的那个集合的和。

我们考虑把每个集合看成一个数。那么，题目就让我们从一堆数中选一些数，使得它们的平均值最大。只选最大的那一个数，则答案就是最大的那一个数；但是最大的数可能不止一个，因此要找到所有值最大且互不相交的集合的数量。

找到最大的那个集合，可以直接O(n)DP出来。设f_x表示以x为根的子树中，包含x的所有集合中最大的那个，则有

这样最大的那个集合就是f_x的最大值。

至于互不重叠的限制吗……再DP一遍，当一个f_x达到最大时，计数器++，并将f_x清零。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,val[300100],f[300100],mx=0x8080808080808080,res,head[300100],cnt;
bool vis[300100];
struct node{
    int to,next;
}edge[600100];
void ae(int u,int v){
    edge[cnt].next=head[u],edge[cnt].to=v,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,head[v]=cnt++;
}
void dfs1(int x,int fa){
    f[x]=val[x];
    for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dfs1(edge[i].to,x),f[x]+=max(0ll,f[edge[i].to]);
}
void dfs2(int x,int fa){
    f[x]=val[x];
    for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dfs2(edge[i].to,x),f[x]+=max(0ll,f[edge[i].to]);
    if(f[x]==mx)res++,f[x]=0x8080808080808080;
}
signed main(){
    scanf("%lld",&n),memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)scanf("%lld",&val[i]);
    for(int i=1,x,y;i<n;i++)scanf("%lld%lld",&x,&y),ae(x,y);
    dfs1(1,0);
    for(int i=1;i<=n;i++)mx=max(mx,f[i]);
    dfs2(1,0);
    printf("%lld %lld\n",1ll*res*mx,res);
    return 0;
}

XLVI.[NOI2002]贪吃的九头龙

思路1.

设f[i][j][k]表示：在以i为根的子树上有j个点是归大头吃的，并且第i个点是归第k个头吃的。

但这样做不仅复杂度高（似乎是O(n^5)？），还有个问题：无法保证每个头都至少吃了一个果子。

思路2.

设f[i][j][0/1]表示：在以i为根的子树上有j个点是归大头吃的，并且第i个点 不是(0)/是(1)归大头吃的。

当m=2时，对于一条边来说，只有一边归大头吃而另一边归小头吃时才不会有损失。证明显然。

否则，即m>2，对于一条边来说，只有两边都归大头吃才会有损失。不归大头吃的地方，可以黑白染色直接造成没有任何地方有损失。

答案为f[1][k][1]。复杂度O(n^3)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,p,head[310],cnt,f[310][310][2],g[310][2];
struct node{
    int to,next,val;
}edge[610];
void ae(int u,int v,int w){
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
void dfs(int x,int fa){
    f[x][0][0]=f[x][1][1]=0;
    for(int i=head[x],y;i!=-1;i=edge[i].next){
        if((y=edge[i].to)==fa)continue;
        dfs(y,x);
        for(int j=0;j<=p;j++)for(int u=0;u<2;u++)g[j][u]=0x3f3f3f3f;
        for(int j=0;j<=p;j++)for(int k=0;k<=j;k++)for(int u=0;u<=min(j-k,1);u++)for(int v=0;v<=min(k,1);v++)g[j][u]=min(g[j][u],f[x][j-k][u]+f[y][k][v]+edge[i].val*(m==2?!(u^v):(u&v)));
        for(int j=0;j<=p;j++)for(int u=0;u<2;u++)f[x][j][u]=g[j][u];
    }
//  printf("%d:",x);for(int i=0;i<=p;i++)printf("(%d,%d)",f[x][i][0],f[x][i][1]);puts(""); 
}
int main(){
    scanf("%d%d%d",&n,&m,&p),memset(head,-1,sizeof(head)),memset(f,0x3f3f3f3f,sizeof(f));
    for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
    if(m+p-1>n){puts("-1");return 0;}
    dfs(1,0);
    printf("%d\n",f[1][p][1]);
    return 0;
}

XLV.CF1178F1 Short Colorful Strip

考虑设f[i,j]表示：假设区间[i,j]里面一开始所有格子的颜色都是相同的，那么，染成目标状态共有多少种染法。

我们找到[i,j]中最小的那个颜色，设为mp。则显然，我们下一步要染上mp这种颜色。

设最终在位置p_{mp}上染上了颜色mp。则我们可以在所有这样的区间[k,l]上染上mp（i\leq k\leq p_{mp}\leq l\leq j）。

或许你会以为这意味着f[i,j]=\sum\limits_{k=i}^{p_{mp}}\sum\limits_{l=p_{mp}}^jf[i,k-1]*f[k,l]*f[l+1,j]。

但是，这样是错误的，因为当[k,l]=[i,j]时，f[i,j]便无法从子状态转移过来！

我们考虑拆开f[k,l]。因为再往后的染色中，位置p_{mp}一定没有再被染色过，因此有f[k,l]=f[k,p_{mp}-1]*f[p_{mp}+1,l]。

则f[i,j]=\sum\limits_{k=i}^{p_{mp}}\sum\limits_{l=p_{mp}}^jf[i,k-1]*f[k,p_{mp}-1]*f[p_{mp}+1,l]*f[l+1,j]。

特殊定义一下，对于f[i,j]，如果i>j，则f[i,j]=1。这也是为了转移的正确（在应用上述式子时可能会调用到这样的f[i,j]。

上面的转移是O(n^4)的；但当我们拆开两个\sum，就可以把它化成O(n^3)的。

前后两个括号内的内容互不干涉，故可以分开计算。

复杂度O(n^3)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,num[510],f[510][510];
int main(){
    scanf("%d%d",&n,&n);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]);
    for(int i=1;i<=n+1;i++)for(int j=0;j<i;j++)f[i][j]=1;
    for(int i=1;i<=n;i++)f[i][i]=1;
    for(int l=2;l<=n;l++)for(int i=1,j=i+l-1;j<=n;i++,j++){
        int mp=i;
        for(int k=i;k<=j;k++)if(num[k]<=num[mp])mp=k;
        int A=0,B=0;
        for(int k=mp;k>=i;k--)(A+=(1ll*f[i][k-1]*f[k][mp-1]%mod))%=mod;
        for(int l=mp;l<=j;l++)(B+=(1ll*f[mp+1][l]*f[l+1][j]%mod))%=mod;
        f[i][j]=1ll*A*B%mod;
    }
    printf("%d\n",f[1][n]);
    return 0;
} 

XLVI.CF1178F2 Long Colorful Strip

首先，每一次染色，最多把一整段连续的同色格子，分成了三段。

并且，明显我们可以把连续的同色格子，直接看作一个。

这就意味着，在这么压缩后，有m<2n。

这就意味着O(m^3)的复杂度是可以接受的。

还是考虑和前一道题一样的DP。

但是这题，并非所有的f[i,j]都是合法的；只有对于每一种颜色，它所有的格子要么全都在段内，要么全都在段外，这样的f[i,j]才是合法的。因为，两个格子只要从什么时候开始颜色不一样了，那它们的颜色也会一直不一样下去。

考虑如何转移。

因为每种颜色都可能出现了不止一次，所以对于一种颜色c，我们有必要记录它出现的最左端mn_c与最右端mx_c。

则转移时的左右两端仍然可以采取和上一问一模一样的转移方式，即

同时，对于区间[mn_{mp},mx_{mp}]内的非mp的所有连续格子段[p_x,q_x]，我们也都应该计算它们的贡献。

因此我们最终得到的是

复杂度仍是O(n^3)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,num[1000100],f[1010][1010],mn[1010],mx[1010];
int main(){
    scanf("%d%d",&n,&m);
    memset(mn,0x3f3f3f3f,sizeof(mn));
    for(int i=1;i<=m;i++){
        scanf("%d",&num[i]);
        if(num[i]==num[i-1])i--,m--;
    }
    if(m>2*n){puts("0");return 0;}
//  for(int i=1;i<=m;i++)printf("%d ",num[i]);puts("");
    for(int i=1;i<=m;i++)mx[num[i]]=max(mx[num[i]],i),mn[num[i]]=min(mn[num[i]],i);
//  for(int i=1;i<=n;i++)printf("%d %d\n",mx[i],mn[i]);
    for(int i=1;i<=m+1;i++)for(int j=0;j<i;j++)f[i][j]=1;
    for(int l=1;l<=m;l++)for(int i=1,j=i+l-1;j<=m;i++,j++){
        int mp=0x3f3f3f3f;
        for(int k=i;k<=j;k++)mp=min(mp,num[k]);
        if(mn[mp]<i||mx[mp]>j)continue;
        int A=0,B=0;
        for(int k=mn[mp];k>=i;k--)(A+=(1ll*f[i][k-1]*f[k][mn[mp]-1]%mod))%=mod;
        for(int l=mx[mp];l<=j;l++)(B+=(1ll*f[mx[mp]+1][l]*f[l+1][j]%mod))%=mod;
        f[i][j]=1ll*A*B%mod;
//      printf("(%d,%d):\n",i,j);
        for(int p=mn[mp]+1,q=mn[mp];p<mx[mp];){
            while(q<j&&num[q+1]!=mp)q++;
//          printf("(%d,%d)\n",p,q);
            f[i][j]=1ll*f[i][j]*f[p][q]%mod;
            q++,p=q+1;
        }
//      printf("%d\n",f[i][j]);
    }
    printf("%d\n",f[1][m]);
    return 0;
} 

XLVII.CF906C Party

DP是门艺术。

处理一下：

这其中，上一行的DP值可以看作是常量。

这样复杂度是O(n^4)，铁定过不去。

但如果我们把高斯消元的矩阵列出来(5\times5)：

更大一点：

也就是说，它是一个非常稀疏的矩阵，并且非零元素只分布在主对角线两侧！

在这种特殊矩阵上高斯消元只需要消对角线两侧的位置即可，复杂度是O(n)的。

则总复杂度是O(n^2)的。

另外，从点(X,Y)出发走到第n行，可以看作是从第X行的任何点出发，走到点(n,Y)的方案数。

代码：

#include<bits/stdc++.h> 
using namespace std;
int n,m,X,Y;
double f[1010],g[1010][1010];
void Giaos(){
//  for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%lf ",g[i][j]);puts("");}puts("");
    for(int i=1;i<n;i++){
        /*int mp=i;
        for(int j=i+1;j<=min(n,i+2);j++)if(fabs(g[j][i])>fabs(g[mp][i]))mp=j;
        if(mp!=i){
            for(int j=i;j<=min(n,i+2);j++)swap(g[mp][j],g[i][j]);
            swap(g[mp][n+1],g[i][n+1]);
        }
        assert(mp==i);*/
        double tmp=g[i+1][i]/g[i][i];
        g[i+1][i]=0,g[i+1][i+1]-=tmp*g[i][i+1],g[i+1][n+1]-=tmp*g[i][n+1];
    }
//  for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%lf ",g[i][j]);puts("");}puts("");
    f[n]=g[n][n+1]/g[n][n];
    for(int i=n-1;i>=1;i--)f[i]=(g[i][n+1]-g[i][i+1]*f[i+1])/g[i][i];
}
int main(){
    scanf("%d%d%d%d",&m,&n,&X,&Y),m-=X-1,X=1;
    if(m==1){puts("0");return 0;}
    if(n==1){printf("%d\n",(m-1)*2);return 0;}
    for(int i=1;i<m;i++){
        g[1][1]=2,g[1][2]=-1,g[1][n+1]=f[1]+3;
        g[n][n]=2,g[n][n-1]=-1,g[n][n+1]=f[n]+3;
        for(int j=2;j<n;j++)g[j][j-1]=g[j][j+1]=-1,g[j][j]=3,g[j][n+1]=f[j]+4;
        Giaos();
    }
    printf("%lf\n",f[Y]);
    return 0;
}

2. 因为“保留4位小数”，所以……

跑50遍最普通的DP完事。

代码：

#include<bits/stdc++.h> 
using namespace std;
int n,m,X,Y;
double f[1010][1010];
int main(){
    scanf("%d%d%d%d",&m,&n,&X,&Y),m-=X-1,X=1;
    if(m==1){puts("0");return 0;}
    if(n==1){printf("%d\n",(m-1)*2);return 0;}
    for(int i=1;i<m;i++)for(int tmp=1;tmp<=50;tmp++)for(int j=1;j<=n;j++){
        if(j==1)f[i][j]=(f[i][j+1]+f[i][j]+f[i-1][j])/3+1;
        else if(j==n)f[i][j]=(f[i][j-1]+f[i][j]+f[i-1][j])/3+1;
        else f[i][j]=(f[i-1][j]+f[i][j]+f[i][j-1]+f[i][j+1])/4+1;
    }
    printf("%lf\n",f[m-1][Y]);
    return 0;
}

L.CF53E Dead Ends