目录

0x51-线性DP：

a.[√] Mr Youngs Picture Permutations

sol:

考虑限制要求：每一排从左往右必须身高递减，每一列从第一排到最后一排身高也必须递减。

则可以发现填数时必须保证：如果从大往小填数，现在填第i行，则第i-1行填了的数必须多于第i行填了的数。

所以可以直接利用这样一种关系进行转移即可。

code：

#include
    
     #include
     
      #include
      
       using namespace std;int k,a[6],n[6],f[31][16][11][9][7];int main(){    while(cin>>k) {        if(k==0)break;        memset(n,0,sizeof(n));        memset(f,0,sizeof(f));        for(int i=1;i<=k;i++) scanf("%d",&n[i]);        f[0][0][0][0][0]=1;        for(a[1]=0;a[1]<=n[1];a[1]++)            for(a[2]=0;a[2]<=n[2];a[2]++)                for(a[3]=0;a[3]<=n[3];a[3]++)                    for(a[4]=0;a[4]<=n[4];a[4]++)                        for(a[5]=0;a[5]<=n[5];a[5]++) {                            int t=f[a[1]][a[2]][a[3]][a[4]][a[5]];                            if(a[1]
       
        a[2]) f[a[1]][a[2]+1][a[3]][a[4]][a[5]]+=t;                            if(a[3]
        
         a[3]) f[a[1]][a[2]][a[3]+1][a[4]][a[5]]+=t;                            if(a[4]
         
          a[4]) f[a[1]][a[2]][a[3]][a[4]+1][a[5]]+=t; if(a[5]
          
           a[5]) f[a[1]][a[2]][a[3]][a[4]][a[5]+1]+=t; } cout<
           
            <
           
          
         
        
       
      
     
    

b.[√] LCIS

sol:

结合LIS和LCS的经典解法，可以设计\(f[i][j]\)表示：

​ A数列的前i个，B数列的前j个中，可以构成的以b[j]为结尾的LCIS长度。

考虑转移：

\[ f[i][j]=f[i-1][j]\ (A[i]!=B[j])\\ f[i][j]=max_{0<=k<j,B[k]<B[j]}\lbrace{f[i-1][k]}\rbrace+1\ (A[i]==B[j])\\ \]

可以发现直接转移为\(n^3\)。

实际上可以发现，可以用一个变量Max来维护\(f[i-1][]\)的最大值。

每次更新完\(f[i][j]\)，只需新加入一个\(f[i-1][j]\)即可。

而为了保证Max所代表的LCIS能够在后面被接上，则更新Max前需判断是否\(A[i]>B[j]\)。

code：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define RG register#define IL inline#define LL long long#define DB doubleusing namespace std;IL int gi() {   RG int x=0,w=0; char ch=getchar();   while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}   while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();   return w?-x:x;}const int N=510;int n,m,Max,ans,a[N],b[N],f[N][N],p[N][N];IL void print(int x,int y) {    while(a[x]!=b[y]) --x;    if(p[x][y]) print(x-1,p[x][y]);    printf("%d ",a[x]);}int main(){    RG int i,j,y,T=1;    while(T--) {        for(i=1,n=gi();i<=n;++i) a[i]=gi();        for(i=1,m=gi();i<=m;++i) b[i]=gi();        memset(f,0,sizeof(f));        memset(p,0,sizeof(p));        for(i=1;i<=n;++i) {            for(j=1,y=Max=0;j<=m;++j) {                f[i][j]=f[i-1][j];                if(a[i]>b[j]&&f[i-1][j]>Max) Max=f[i][j],y=j;                // 此处用a[i]>b[j]，是为了保证后面如果存在a[i]==b[j]时，b[j]>a[i]，很巧妙                if(a[i]==b[j]) f[i][j]=Max+1,p[i][j]=y;            }        }        for(j=1,ans=0;j<=m;++j)            if(f[n][j]>ans) ans=f[n][j],y=j;        printf("%d\n",ans);        if(ans) print(n,y);        putchar('\n');    }    return 0;}// 最长公共上升子序列
        
       
      
     
    

c.[√] Making the Grade

sol:

只需考虑不下降的构造即可，不上升的构造同理。

设\(f[i][x]\)表示填了前i个数，第i个数填的是x时的最小答案。

那么容易得到转移方程为：

\[ f[i][x]=min_{0<=k<=x}\lbrace{f[i-1][k]}\rbrace+\arrowvert A[i]-x\arrowvert \]

但是注意到值域有\(10^9\)，所以还不能直接做。

这时需要意识到一个结论：改造出来的数列的元素全是原来数列里有的数。

证明：数学归纳法。

对于n=1，显然成立。

对于n=k−1时，假设其满足由原数列的数构成最优解。那么，考虑对于n=k。

当\(A_n≥B_{n−1}\)时（B为之后的数列）显然直接用\(A_n\)最优。

当\(A_n ＜ B_{n-1}\)时有两种选择:

① 填\(B_{n-1}\)。

② 把\(B_j…B_n\)全部向下调整为t。此时对于\(A_j…A_n\)的中位数mid，

如果存在\(mid ≥ B_{j-1}\),则\(t=mid\)时最优，否则\(t=B_{j-1}\)时最优。

综上，无论哪种最优情况下都为A[]中出现过的数，命题成立。

基于此，则可以直接把能填的数个数范围缩小到2000，加上与上一题类似的用变量min维护f最小值，在直接转移，做到\(n^2\)

code:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define RG register#define IL inline#define LL long long#define DB doubleusing namespace std;IL int gi() {   RG int x=0,w=0; char ch=getchar();   while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}   while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();   return w?-x:x;}const int N=2e3+7;const int inf=0x3f3f3f3f;LL ans1,ans2,f[N][N];int n,a[N],b[N];IL bool cmp(int a,int b) {return a>b;}IL void DP() {    RG int i,j;    RG LL Min;    memset(f,0,sizeof(f));    for(i=1;i<=n;++i) {        for(j=1,Min=inf;j<=n;++j) {            Min=min(Min,f[i-1][j]);            f[i][j]=Min+abs(a[i]-b[j]);        }    }}int main(){    RG int i;    for(i=1,n=gi();i<=n;++i) a[i]=b[i]=gi();    sort(b+1,b+n+1);    ans1=ans2=inf;    for(i=1,DP();i<=n;++i) ans1=min(ans1,f[n][i]);    sort(b+1,b+n+1,cmp);    for(i=1,DP();i<=n;++i) ans2=min(ans2,f[n][i]);      printf("%lld\n",min(ans1,ans2));    return 0;}
        
       
      
     
    

d.[√] Mobile Service

sol:

先考虑最直接的状态：\(f[i][x[y][z]\)表示解决了前面i个请求，三个服务员分别位于x,y,z时的最小花费。

那么容易写得转移：

\[ f[i+1][p_{i+1}][y][z]=min(f[i+1][p_{i+1}][y][z],f[i][x][y][z]+cost(x,p_{i+1}))\\ f[i+1][x][p_{i+1}][z]=min(f[i+1][x][p_{i+1}][z],f[i][x][y][z]+cost(y,p_{i+1}))\\ f[i+1][x][y][p_{i+1}]=min(f[i+1][x][y][p_{i+1}],f[i][x][y][z]+cost(z,p_{i+1}))\\ \]

时空复杂度为：O(\(1000*200^3\)),显然不行。

但是发现实际上并不需要记录三个人的位置，只需记录两个人的即可，第三者必然在\(p_i\)位置上。

所以，\(f[i][x[y]\)表示解决了前面i个请求，两个服务员分别位于x,y，另一个位于\(p_i\)时的最小花费。

转移为：

\[ f[i+1][p_i][y]=min(f[i+1][p_i][y],f[i][x][y]+cost(x,p_{i+1}))\\ f[i+1][x][p_i]=min(f[i+1][x][p_i],f[i][x][y]+cost(y,p_{i+1}))\\ f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+cost(p_i,p_{i+1}))\\ \]

code:

#include 
    
     using namespace std;inline int gi() {    int x=0, w=0; char ch=0;    while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=1; ch=getchar();}    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}    return w?-x:x;}const int Pos=210;const int N=1010;int T,L,n,ans,f[N][Pos][Pos],c[Pos][Pos],pos[N];int main (){    T=gi();    while(T--) {        ans=0x3f3f3f3f;        memset(c,0,sizeof(c));        memset(pos,0,sizeof(pos));         memset(f,0x3f3f3f3f,sizeof(f));        L=gi(),n=gi();        for(int i=1;i<=L;++i)            for(int j=1;j<=L;++j) c[i][j]=gi();        for(int i=1;i<=n;++i) pos[i]=gi();        pos[0]=3,f[0][1][2]=0;        for(int k=0;k
    

e.[√] 传纸条

sol:

直观想法四维DP：

设\(f[i,j,p,q]\)表示从小渊传到小轩的纸条到达(i,j)，从小轩传给小渊的纸条到达(p,q)的路径上取得的最大的好心程度和。

那么转移为：

\(f[i,j,p,q]=max( f[i,j-1,p-1,q] , f[i-1,j,p,q-1] , f[i,j-1,p,q-1] , f[i-1,j,p-1,q] )+a[i,j]+a[p,q]\)

这样的话Luogu上现在应该是过不了了（以前可以）。

由上一题可以得到启发，若记路径长度为k，始终存在：\(i+j=p+q=k+2\)。

所以只需记录一个长度k，两次分别的行数i，p即可，复杂度降为\(O(n^3)\)。

code:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define RG register#define IL inline#define LL long long#define DB doubleusing namespace std;IL int gi() {   RG int x=0,w=0; char ch=getchar();   while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}   while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();   return w?-x:x;}const int N=51;int n,m,a[N][N],f[N<<1][N][N];int main(){    RG int i,j,k;    n=gi(),m=gi();    for(i=1;i<=n;++i)        for(j=1;j<=m;++j) a[i][j]=gi();    f[0][1][1]=a[1][1];    for(k=1;k<=n+m-2;++k)        for(i=1;i<=n&&i<=k+1;++i)            for(j=1;j<=n&&j<=k+1;++j) {                if(k+2-i>n||k+2-j>m) continue;                f[k][i][j]=max(f[k-1][i][j],max(f[k-1][i-1][j-1],max(f[k-1][i-1][j],f[k-1][i][j-1])));                f[k][i][j]+=a[i][k+2-i]+a[j][k+2-j]*(i!=j);            }    printf("%d\n",f[n+m-2][n][n]);    return 0;}
        
       
      
     
    

f.[√] I-country

SGU进不去。

题面：

在N×M的矩阵中，每个格子有一个权值，要求寻找一个包含K个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的），使这个连通块中的格子的权值和最大。求出这个最大的权值和，并给出连通块的具体方案。N,M<=15,K<=225。

大概写一下这个题目做法巧妙的地方：

注意到了凸联通块的特性：

任何一个凸联通块可以划分成连续若干行。且每行的左端点列号先递减，再递增，右端点列号先递增，再递减。

那么这样我们只要把这些特点设进状态里，就可以较容易的实现DP了。

设\(F[i,j,l,r,p,q]\)表示前i行选了j个格子，第i行选了l到r，左右两边的单调性分别为p,q时的答案。

① 左边界递减，右边界递增

\[ F[i,j,l,r,1,0]=∑_{p=l}^rA[i,p]+F[i−1,0,0,0,1,0]\ \ \ \ if\ (j=r-l+1>0)\\ F[i,j,l,r,1,0]=∑_{p=l}^rA[i,p]+max_{l≤p≤q≤r}\lbrace F[i−1,j−(r−l+1),p,q,1,0]\ \ \ \ if\ (j>r-l+1>0)\rbrace \]

② 左边界递减，右边界递减

\[ F[i,j,l,r,1,1]=∑_{p=l}^rA[i,p]+max_{l≤p≤r≤q}\lbrace F[i−1,j−(r−l+1),p,q,1,0/1]\rbrace \]

③ 左边界递增，右边界递增

\[ F[i,j,l,r,0,0]=∑_{p=l}^rA[i,p]+max_{p≤l≤q≤r}\lbrace F[i−1,j−(r−l+1),p,q,0/1,0]\rbrace \]

④ 左边界递增，右边界递减

\[ F[i,j,l,r,0,1]=∑_{p=l}^rA[i,p]+max_{p≤l≤r≤q}\lbrace F[i−1,j−(r−l+1),p,q,0/1,0/1]\rbrace \]

最后 \(ans=max \lbrace F[i,K,l,r,0/1,0/1] \rbrace\)

code:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define RG register#define IL inline#define LL long long#define DB doubleusing namespace std;IL int gi() {   RG int x=0,w=0; char ch=getchar();   while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}   while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();   return w?-x:x;}const int N=16;int n,m,k,ans,a[N][N],s[N][N][N],f[N][N*N][N][N][2][2];struct mem{int l,r,x,y;}g[N][N*N][N][N][2][2];void print(int i,int j,int l,int r,mem s) {    if(!j) return;    print(i-1,j-(r-l+1),s.l,s.r,g[i-1][j-(r-l+1)][s.l][s.r][s.x][s.y]);    for(RG int o=l;o<=r;++o) printf("%d %d\n",i,o);}int main(){    RG int i,j,l,r,p,q,x,y;    n=gi(),m=gi(),k=gi();    for(i=1;i<=n;++i)        for(j=1;j<=m;++j) a[i][j]=gi();    if(!k) return puts("0"),0;    for(i=1;i<=n;++i)        for(l=1;l<=m;++l)            for(r=l;r<=m;++r) s[i][l][r]=s[i][l][r-1]+a[i][r];    for(i=1;i<=n;++i)        for(j=1;j<=k;++j)            for(l=1;l<=m;++l)                for(r=l;r<=m;++r)                    if(j==r-l+1) f[i][j][l][r][1][0]=s[i][l][r];                    else if(j>r-l+1) {                        RG int res;                        for(p=l,res=0;p<=r;++p)                            for(q=p;q<=r;++q)                                if(j-(r-l+1)>=q-p+1&&f[i-1][j-(r-l+1)][p][q][1][0]>res)                                     res=f[i-1][j-(r-l+1)][p][q][1][0],g[i][j][l][r][1][0]=(mem){p,q,1,0};                        f[i][j][l][r][1][0]=res+s[i][l][r];                        for(p=l,res=0;p<=r;++p)                            for(q=r;q<=m;++q)                                if(j-(r-l+1)>=q-p+1)                                    for(y=0;y<=1;++y)                                        if(f[i-1][j-(r-l+1)][p][q][1][y]>res)                                            res=f[i-1][j-(r-l+1)][p][q][1][y],g[i][j][l][r][1][1]=(mem){p,q,1,y};                        f[i][j][l][r][1][1]=res+s[i][l][r];                        for(p=1,res=0;p<=l;++p)                            for(q=l;q<=r;++q)                                if(j-(r-l+1)>=q-p+1)                                    for(x=0;x<=1;++x)                                        if(f[i-1][j-(r-l+1)][p][q][x][0]>res)                                            res=f[i-1][j-(r-l+1)][p][q][x][0],g[i][j][l][r][0][0]=(mem){p,q,x,0};                        f[i][j][l][r][0][0]=res+s[i][l][r];                        for(p=1,res=0;p<=l;++p)                            for(q=r;q<=m;++q)                                if(j-(r-l+1)>=q-p+1)                                    for(x=0;x<=1;++x)                                        for(y=0;y<=1;++y)                                            if(f[i-1][j-(r-l+1)][p][q][x][y]>res)                                                res=f[i-1][j-(r-l+1)][p][q][x][y],g[i][j][l][r][0][1]=(mem){p,q,x,y};                        f[i][j][l][r][0][1]=res+s[i][l][r];                    }    RG int f1,f2,f3,f4,f5;    for(i=1;i<=n;++i)        for(l=1;l<=m;++l)            for(r=l;r<=m;++r)                for(x=0;x<=1;++x)                    for(y=0;y<=1;++y)                        if(ans
        
       
      
     
    

g.[√] Cookies

sol：

这道题比较综合。

首先需要一个贪心策略：贪婪度大的孩子需要更多的饼干。

那么把孩子按照贪婪度从大到下排序后，每个孩子得到的饼干数单调递减。

然后考虑设\(f[i,j]\)表示前i个孩子发了j个饼干的最小怨气和。

这个时候发现，由于无法确定之前到底有有多少个比它多，所以并不好进行转移。

这里涉及到的是这道题的第二个重点—等效手法对状态进行缩放。

分类讨论一下：

①、如果第i个孩子拿到了数量大于1的饼干。

​ 那么等价于前i个孩子1人分了1块后，把前j-i块分给了前i个人，这样相对大小不变，不影响答案。

②、 如果第i个孩子拿到了数量等于1的饼干。

​ 那么可以考虑枚举前面有多少人也只有1块饼干，直接计算贡献。

综上，状态转移可写为：

\[ f[i,j]=min\lbrace{f[i,j-i],min_{0≤k＜i}\{ f[k,j-(i-k)]+k*\sum_{p=k+1}^{i}{g[p]}\}}\rbrace \]

code:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define RG register#define IL inline#define LL long long#define DB doubleusing namespace std;IL int gi() {   RG int x=0,w=0; char ch=getchar();   while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}   while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();   return w?-x:x;}const int N=33;const int M=5003;const int inf=0x3f3f3f3f;int n,m,ans[N],s[N][N],f[N][M],pr[N][M][2];struct GG{int a,id;}g[N];IL bool cmp(GG x,GG y) {return x.a>y.a;}void allocate(int x,int y,int cnt) {    if(!x||!y) return;    if(pr[x][y][0]==x) allocate(pr[x][y][0],pr[x][y][1],cnt+1);    else {        RG int i;        for(i=pr[x][y][0]+1;i<=x;++i) ans[g[i].id]=cnt;        allocate(pr[x][y][0],pr[x][y][1],cnt);    }}int main(){    RG int i,j,k;    n=gi(),m=gi();    for(i=1;i<=n;++i) g[i].a=gi(),g[i].id=i;    sort(g+1,g+n+1,cmp);    for(i=1;i<=n;++i)        for(j=i;j<=n;++j) s[i][j]=s[i][j-1]+g[j].a;             memset(f,0x3f,sizeof(f));    f[0][0]=0;    for(i=1;i<=n;++i)        for(j=i;j<=m;++j) {            f[i][j]=f[i][j-i];            if(f[i][j]!=inf) pr[i][j][0]=i,pr[i][j][1]=j-i;            for(k=0;k
         
          f[k][j-i+k]+k*s[k+1][i]) f[i][j]=f[k][j-i+k]+k*s[k+1][i],pr[i][j][0]=k,pr[i][j][1]=j-i+k; } printf("%d\n",f[n][m]); for(i=1,allocate(n,m,0);i<=n;++i) printf("%d ",ans[i]+1); return 0;}