$CH$ $0x50$ & $0x51$ 做题记录

2023-02-18 10:11:49

[X]$Mr.Young's\ Picture\ Permutations$

前面这儿写了挺多道辣,,,懒得写辣$QAQ$

(后面所有同上都是同这个$QwQ$

[X]$LCIS$

做过了,看这儿

$upd$:,,,这题有猫饼,不呲呲快读,用快读会$T$一个点,,,然后我下了数据下来发现明明是数据的锅,,,?我感觉它给我的这个数据明明就不够,,,?但反正我改成$scanf$或者$cin$就过去了,,,什么$sd$玩意$QAQ$

[X]$Mobile\ Service$

无脑$dp$入门题,,,?

设$f_{i,j,k}$表示时间$i$没站在$d_{i}$的两个人的坐标,然后只要记得判下说任意俩人不能站在同一个位置就欧克,,,$QwQ$

然后$i$显然是不需要的只是为了方便表述设的这一维,,,实际$code$中是不会有这一维的昂$QwQ$

哦话说,这样儿说着很简单,其实好像是要证个东西,,,就三个人的坐标一定都是移动到$d_{i}$,不可能移动到别的位置,,,$umm$过于显然不证了,,,只是$cue$下其实是要证这个东西的来着$QAQ$

嗷还有一个就,这个$i$显然是要滚掉的嘛,正常方法应该就滚成[0/1]就欧克,然后因为$gql$没有脑子,就直接暴力开了个$f$再开了个$g$,当然显然的是开[0/1]还是好写,因为可以用$memset$,常数应该会小些,,,?不过麻油关系反正过得去就成$bushi$

$over$
#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int L=+,N=+;

int l,n,f[N][N],g[N][N],pos[L],cst[L][L],as;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

int main()

{

    freopen("5102.in","r",stdin);freopen("5102.out","w",stdout);

    l=read();n=read()+;rp(i,,l)rp(j,,l)cst[i][j]=read();pos[]=;pos[]=;pos[]=;memset(f,,sizeof(f));as=f[][];f[][]=f[][]=;

    rp(i,,n)

    {

        pos[i]=read();rp(j,,l)rp(k,,l)g[j][k]=f[j][k],f[j][k]=f[][];

        rp(j,,l)

            rp(k,,l)

            {

                if(j==k)continue;

                if(k!=pos[i] && pos[i-]!=pos[i])f[k][pos[i-]]=f[pos[i-]][k]=min(f[k][pos[i-]],g[j][k]+cst[j][pos[i]]);

                if(j!=pos[i] && pos[i-]!=pos[i])f[j][pos[i-]]=f[pos[i-]][j]=min(f[j][pos[i-]],g[j][k]+cst[k][pos[i]]);

                if(j!=pos[i] && k!=pos[i])f[j][k]=f[k][j]=min(f[j][k],g[j][k]+cst[pos[i-]][pos[i]]);

            }

    }

    rp(i,,l)rp(j,,l)if(i!=j && pos[n]!=i && pos[n]!=j)as=min(as,f[i][j]);printf("%d\n",as);

    return ;

}

[X]$Making\ the\ Grade$

做过辣,看这儿

[X]传纸条

又双叒是个$dp$无脑入门题,,,?

首先四维$dp$过于显然不想写了,,,

然后考虑四位压成三维,依然太显然了,,,不写辣/$kel\ kel\ kel$

反正大致思路就上面这样儿的,懒得写了$over$

对了,这个$code$是我去年9月份写的了(,,,我那个时候做的题居然这么水,,,?太菜了嘤嘤嘤),,,所以贼丑但我也懒得改了$QAQ$

#include<bits/stdc++.h>

using namespace std;

int a[][];

int f[][][];

int read()

{

    char ch;

    int x=;

    bool o=;

    ch=getchar();

    while(ch!='-' && (ch<'' || ch>''))ch=getchar();

    if(ch=='-')o=;

    while(ch>='' && ch<='')

    {

        x=(x<<)+(x<<)+(ch^'');

        ch=getchar();

    }

    if(o==)return -x;

    return x;

}

int main()

{

    int m,n;

    m=read();

    n=read();

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++)a[i][j]=read();

    memset(f,-,sizeof(f));

    f[][][]=;

    for(int k=;k<m+n;k++)

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

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

            {

                f[k][i][j]=max(f[k][i][j],max(f[k-][i][j],max(f[k-][i-][j],max(f[k-][i][j-],f[k-][i-][j-]))))+a[k-i][i]+a[k-j][j];

                if(f[k][i][j]==a[k-i][i]+a[k-j][j]-)f[k][i][j]=-;

            }

    printf("%d",f[m+n-][n-][n]);

    return ;

}

[X]$I-country$

比起前面几题的话,相对而言还是比较有趣的辣,,,?

$so$大概港下$QwQ$

首先考虑怎么设状态?

首先理解下题意昂,这个所谓凸壳,其实就说要求左端点先递减后递增,右端点先递增后递减

于是显然就考虑状态为$f_{i,j,l,r,0/1,0/1}$,表示选到第$i$行,选了$j$个,左端点到$l$,右端点到$r$,左端点递增递减状态,右端点递增递减状态

转移,表述比较麻烦但并不难想,,,?就先不写辣$QwQ$

欧克然后就做完了,,,然而因为$gql$过于傻逼所以依然$WA$了$inf$次,,,我要死了呜呜呜

想提两个要注意的点$QwQ$

第一个是说,要考虑到可能存在前面若干行不选和后面若干行不选这样儿的情况(像我就非常,没有脑子,直接就又多$for$了下就非常暴力地搞掉了$QwQ$

第二个是说,要注意到还有个隐藏条件,就是相邻两行之间必须有交点,,,记得判下不然会被#4给搞掉应该$QAQ$

嗷还有就是我没写怎么记录方案,,,比较正常的想法应该就过程中瞎搞下应该就欧克了,,,?

然后因为$gql$没有脑子,,,打完才想起来要记录方案,,,然后就懒得瞎搞了,直接在结尾非常暴力地搞了一通,$over$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define int long long

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,K=;

int n,m,kk,dat[N][N],f[N][K][N][N][][],sum[N][N],as,prel,prer,opl,opr,tmpn;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

signed main()

{

//    freopen("5104.in","r",stdin);freopen("5104.out","w",stdout);

    n=read();m=read();kk=read();rp(i,,n)rp(j,,m)sum[i][j]=sum[i][j-]+(dat[i][j]=read());

    rp(i,,n)

        rp(j,,min(m*i,kk))

            rp(l,,m)

                rp(r,l,m)

                {

                    if(j<r-l+)continue;

                    f[i][j][l][r][][]=f[i][j][l][r][][]=f[i][j][l][r][][]=f[i][j][l][r][][]=sum[i][r]-sum[i][l-];

                    if(i==)

                    {

                        if(j!=r-l+)f[i][j][l][r][][]=f[i][j][l][r][][]=f[i][j][l][r][][]=f[i][j][l][r][][]=;

                        continue;

                    }

                    rp(ll,,r)

                        rp(rr,l,m)

                        {

                            if(j<rr-ll++r-l+)continue;if(ll>r || l>rr)continue;

                            if(ll>=l)

                            {

                                if(rr>=r)f[i][j][l][r][][]=max(max(f[i-][j-(r-l+)][ll][rr][][],f[i-][j-(r-l+)][ll][rr][][])+sum[i][r]-sum[i][l-],f[i][j][l][r][][]);

                                if(rr<=r)f[i][j][l][r][][]=max(f[i-][j-(r-l+)][ll][rr][][]+sum[i][r]-sum[i][l-],f[i][j][l][r][][]);

                            }

                            if(ll<=l)

                            {

                                if(rr>=r)f[i][j][l][r][][]=max(max(max(f[i-][j-(r-l+)][ll][rr][][],f[i-][j-(r-l+)][ll][rr][][]),max(f[i-][j-(r-l+)][ll][rr][][],f[i-][j-(r-l+)][ll][rr][][]))+sum[i][r]-sum[i][l-],f[i][j][l][r][][]);

                                if(rr<=r)f[i][j][l][r][][]=max(max(f[i-][j-(r-l+)][ll][rr][][],f[i-][j-(r-l+)][ll][rr][][])+sum[i][r]-sum[i][l-],f[i][j][l][r][][]);

                            }

                        }

                }

    rp(i,,n)rp(l,,m)rp(r,l-,m){ri tmp=as;as=max(as,max(max(f[i][kk][l][r][][],f[i][kk][l][r][][]),max(f[i][kk][l][r][][],f[i][kk][l][r][][])));if(tmp!=as)tmpn=i;}

    printf("Oil : %lld\n",as);

    n=tmpn;

    rp(l,,m)

        rp(r,l,m)

        {

            if(f[n][kk][l][r][][]==as){prel=l,prer=r,opl=,opr=;as-=sum[n][r]-sum[n][l-];kk-=r-l+;l=m+;break;}

            if(f[n][kk][l][r][][]==as){prel=l,prer=r,opl=,opr=;as-=sum[n][r]-sum[n][l-];kk-=r-l+;l=m+;break;}

            if(f[n][kk][l][r][][]==as){prel=l,prer=r,opl=,opr=;as-=sum[n][r]-sum[n][l-];kk-=r-l+;l=m+;break;}

            if(f[n][kk][l][r][][]==as){prel=l,prer=r,opl=,opr=;as-=sum[n][r]-sum[n][l-];kk-=r-l+;l=m+;break;}

        }

    rp(i,prel,prer)printf("%lld %lld\n",n,i);

    my(i,n-,)

        rp(l,,m)

            rp(r,l,m)

            {

                if(opl && prel<l)continue;if(!opl && prel>l)continue;if(opr && prer<r)continue;if(!opr && prer>r)continue;if(prel>r || l>prer)continue;

                if(f[i][kk][l][r][][]==as)

                    if(!opr)

                    {

                        as-=sum[i][r]-sum[i][l-];prel=l,prer=r,opl=,opr=;kk-=r-l+;l=m+;r=m+;

                        rp(p,prel,prer)printf("%lld %lld\n",i,p);continue;

                    }

                if(f[i][kk][l][r][][]==as)

                {

                    as-=sum[i][r]-sum[i][l-];prel=l,prer=r,opl=,opr=;kk-=r-l+;l=m+;r=m+;

                    rp(p,prel,prer)printf("%lld %lld\n",i,p);continue;

                }

                if(f[i][kk][l][r][][]==as)

                    if(opl && !opr)

                    {

                        as-=sum[i][r]-sum[i][l-];prel=l,prer=r,opl=,opr=;kk-=r-l+;l=m+;r=m+;

                        rp(p,prel,prer)printf("%lld %lld\n",i,p);continue;

                    }

                if(f[i][kk][l][r][][]==as)

                    if(opl)

                    {

                        as-=sum[i][r]-sum[i][l-];prel=l,prer=r,opl=,opr=;kk-=r-l+;l=m+;r=m+;

                        rp(p,prel,prer)printf("%lld %lld\n",i,p);continue;

                    }

            }

    return ;

}

/*

  0:递减

  1:递增

  l:先0后1

  r:先1后0

  0<-0/1 1<-1

  1<-0/1 0<-0

*/

[X]$Cookies$

这题挺有趣的,,,就这题和之前做过的一道题有点儿像,,,这个,虽然是道绿但我印象还挺深的,,,因为它是这样儿的,就,有一部分之间是无后效性的,但有一部分是有后效性的,,,

这题也是,首先要想到,显然从多往少安排,所以这时候显然有个小小的贪心,就说$g_{i}$越大的拿到的饼干数越多,于是就先按$g_{i}$排个序,然后考虑设$f_{i,j,k}$表示分到第$i$个孩子了,然后分了$j$个饼干,这一个孩子拿了$k$个饼干,看数据范围,发现$O(NM^{2})$,就不太星$QAQ$

好然后再仔细思考下,假如现在有$m$块,显然先平均分,每人拿到$\left \lfloor \frac{m}{n} \right \rfloor$块,这样儿就能把$m$控制在$n$范围以内,就过辣!

然后就被$hack$辣嘤嘤嘤

来我先$hack$下我的无脑优化想法$QAQ$

比如有5个,分别是$inf,inf,inf,inf,0$,然后有13块饼干

如果先贪心,就先均分,每人2个,剩3个,然后这时候$dp$下,显然是前三个每人拿一个,然后代价就是$3\cdot inf$

但是正解应该是,前四个人每人拿3个,然后最后一个人拿1个,这样儿代价就是0,,,

所以就被$hack$了\$kel\ kel\ kel$

而且上面这个还有个问题在于,可以有相等的,就会导致并不知道到底有多少个比它大的$qwq$

好然后现在整个儿都被$hack$了嘤嘤嘤,,,

重写下解法嘤嘤嘤

这里要考虑,状态缩放,也就是通过等价交换使得时间复杂度变好看

先用下万能的分类讨论法$QwQ$

对了先说下,$i$表示的是第$i$个人,$j$表示的是分了$j$块饼干,$k$表示的是从第$k$个人开始所有人都只有1块

1)第$i$个人获得的饼干数>1

这个可以等价与分配$j-i$个饼干给前$i$个人,每人少拿一块,这个显然是等价的$QwQ$,因为相对大小是不变的(这个就和前面那个均分有点儿像,,,是不是$QwQ$

这样儿转移就可以变成,$f_{i,j}=f_{i-1,j-i}$

2)第$i$个人获得的饼干数=1

直接考虑在它及之前有多少个人只有1块?

这样儿转移就可以变成$f_{i,j}=(f_{k,j-(i-k)}+k\cdot \sum_{p=k+1}^{i}g_{p})_{min}$

综上,转移就是$f_{i,j}=(f_{i-1,j-i},(f_{k,j-(i-k)}+k\cdot \sum_{p=k+1}^{i}g_{p})_{min})_{min}$

就做完啦啦啦啦

昂然后最后输出方案,其实我$jio$得还挺有趣的,但我是瞎搞一通搞出来的,也说不出个什么所以然来,就瞎递归下然后模拟($bushi$下就瞎搞出来了,,,所以具体看$code$趴$QAQ$

嗷对了,,,$gql$在线傻逼了一通,,,大概港下$gql$的$sd$想法昂$QAQ$

是这样儿的,就,假如现在是在进行,$i=1$的枚举$k$的转移,然后假如我在转移到$k$的时候,实际上的那个$f_{k,j-(i-k)}$的那个点也是从$k=1$转移来的,那就会导致$f_{i,j}$变大鸭(就因为本来没有$k$个大于1的,但这儿当做有$k$个了嘛$QwQ$

然后仔细一想发现显然是我傻逼了,,,因为如果有这种情况,我一定吃枣会枚举到$k=1$转移来的点${k}'$,然后就一定会从${k}'$这儿再转下,就不会算重了,,,

其实是个很显然的事儿?主要可能还是$gql$太傻逼了嘤嘤嘤

然后因为$gql$语文太差了所以表述能力贼差可能上一段表述得不是很清楚,,,然而我也懒得重写了,,,如果有问题在评论区港就是了$kk$
#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,M=5e3+;

int n,m,g[N],f[N][M],sum[N],pre[N][M],as[N];

struct nod{int g,id;}node[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(nod gd,nod gs){return gd.g>gs.g;}

il void work(ri n,ri m)

{

    if(!n)return;

    if(pre[n][m]==n){work(pre[n][m],m-n);rp(i,,n)++as[node[i].id];return;}

    work(pre[n][m],m-(n-pre[n][m]));rp(i,pre[n][m]+,n)as[node[i].id]=;return;

}

int main()

{

    //freopen("5105.in","r",stdin);freopen("5105.out","w",stdout);

    n=read();m=read();rp(i,,n)node[i]=(nod){read(),i};sort(node+,node++n,cmp);rp(i,,n)sum[i]=sum[i-]+node[i].g;memset(f,,sizeof(f));f[][]=;

    rp(i,,n)

        rp(j,i,m)

        {

            f[i][j]=f[i][j-i];pre[i][j]=i;

            rp(k,,i-)if(f[i][j]>f[k][j-(i-k)]+(sum[i]-sum[k])*k)pre[i][j]=k,f[i][j]=f[k][j-(i-k)]+(sum[i]-sum[k])*k;

        }

    printf("%d\n",f[n][m]);

    work(n,m);

    rp(i,,n)printf("%d ",as[i]);

    return ;

}

[X]数字组合

无脑$dp$,,,?

考虑设$f_{i,j}$表示前$i$个数拼出$j$的方案数,无脑背包下就好,,,?

$over$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,M=+;

int n,m,a[N],f[M];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

int main()

{

    //freopen("5201.in","r",stdin);freopen("5201.out","w",stdout);

    n=read();m=read();rp(i,,n)a[i]=read();f[]=;

    rp(i,,n)

        my(j,m,a[i])f[j]+=f[j-a[i]];

    printf("%d\n",f[m]);

    return ;

}

背包板子我居然打了10$min$,,,是不是小水题做多了会影响智商昂$TT$

[X]自然数拆分

又是个无脑$dp$,,,

考虑设$f_{i}$表示拼出$i$的方案数,于是有$f_{i}=\sum f_{j}+f_{i-j}$

$over$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define int long long

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int M=+,mod=;

int n,f[M];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

 main()

{

    //freopen("5202.in","r",stdin);freopen("5202.out","w",stdout);

    n=read();f[]=;

    rp(i,,n)rp(j,i,n)f[j]=(f[j]+f[j-i])%mod;

    printf("%lld\n",f[n]->=?f[n]-:mod-);

    return ;

}

完全背包板子昂$QwQ$

[X]$Jury\ Compromise$

做过了,看这儿

[X]$Coins$

做过了,看这儿

[X]石子合并

无脑区间$dp$

设$f_{l,r}$,表示$[l,r]$的最小代价,做完了

几百年前的代码,贼丑,$QAQ$

$upd:$我在$CH$上交了下,发现题目还是有点儿区别,,,最大的区别在这不是个环,,,所以连断环为链都不需要,,,$QAQ$

$over$

#include<bits/stdc++.h>

using namespace std;

int n,m,a[],f[][],f1[][],sum[],q=,ww,e,maxl=,minl=,i,j,l;

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

        a[i+n]=a[i];

    }

    for(i=;i<=*n;i++)sum[i]=sum[i-]+a[i];

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

    {

        for(i=;i<=*n-l+;i++)

        {

            j=i+l-;

            f[i][j]=;

            f1[i][j]=;

            for(int k=i;k<=j-;k++)

            {

                f[i][j]=min(f[i][j],f[i][k]+f[k+][j]+sum[j]-sum[i-]);

                f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+][j]+sum[j]-sum[i-]);

            }

        }

    }

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

    {

        maxl=max(maxl,f1[i][i+n-]);

        minl=min(minl,f[i][i+n-]);

    }

    cout<<minl<<endl<<maxl;

    return ;

}

[X]$Polygon$

做过了,看这儿

[X]金字塔

想到了那个点就不难,不然还是有点儿难度的欸$QAQ$

主要就是要想到一个子树对应一个区间?所以考虑设$f_{l,r}$表示$[l,r]$这个区间作为一颗子树的方案数$QwQ$

然后一个比较有趣的点是考虑怎么转移能保证是不重不漏的$QwQ$,就考虑枚举$[l,r]$中第一颗子树的结束点$k$.然后就有$f_{l,r}=\sum f_{l+1,k-1}\cdot f_{k,r-1}$,当然,还可以从$f_{l-1,r+1}$转移来

综上,就是$f_{l,r}=f_{l-1,r+1}+\sum_{col_{l}=col_{k}}f_{l+1,k-1}\cdot f_{k,r}$(当且仅当col_{l}=col_{r}

记得开$ll$鸭

$over$
#include<bits/stdc++.h>

using namespace std;

#define il inline

#define int long long

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,mod=1e9;

int n,f[N][N];

char str[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il int solve(ri l,ri r)

{

    if(str[l]!=str[r])return ;if(l>r)return ;if(l==r)return ;if(f[l][r]!=-)return f[l][r];

    f[l][r]=;

    rp(i,l+,r-)if(str[l]==str[r])f[l][r]=(f[l][r]+1ll*solve(l+,i-)*solve(i,r)%mod)%mod;

    f[l][r]=(f[l][r]+solve(l+,r-))%mod;

    return f[l][r];

}

 main()

{

    //freopen("5302.in","r",stdin);freopen("5302.out","w",stdout);

    scanf("%s",str+);n=strlen(str+);memset(f,-,sizeof(f));

    printf("%lld\n",solve(,n));

    return ;

}

[X]没有上司的舞会

树形$dp$入门题,,,?

很早以前就听说过这题了但一直没做,,,

直接考虑设$f_{i,0/1}$表示考虑了$i$及它的子树了,$i$这个点去不去的最大快乐值

$over$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+;

int n,h[N],f[N][],head[N],ed_cnt,fa[N],rt;

struct ed{int to,nxt;}edge[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri to,ri fr){edge[++ed_cnt]=(ed){to,head[fr]};head[fr]=ed_cnt;fa[to]=fr;}

il void solve(ri x){e(i,x)solve(t(i)),f[x][]+=max(f[t(i)][],f[t(i)][]),f[x][]+=f[t(i)][];f[x][]+=h[x];return;}

int main()

{

    //freopen("5401.in","r",stdin);freopen("5401.out","w",stdout);

    n=read();rp(i,,n)h[i]=read();rp(i,,n){ri x=read(),y=read();ad(x,y);}

    rp(i,,n)if(!fa[i])rt=i;solve(rt);printf("%d\n",max(f[rt][],f[rt][]));

    return ;

}

[X]选课

无脑树形$dp$入门题,,,?

和上一个差不多,状态一样,只是转移有点儿区别,$over$

$over$

然后弱智$gql$就打了$1.5h$才做完,,,身败名裂了$TT$

就,其实这题和上题还是有点儿区别,,,就根本不用设那个0/1的,,,打了我半天我才发现我题意理解错了,,,你们呆我屎猫

其实是个无脑树形背包,,,$get$错了题意自然而然题目类型也判断的是错的昂$QAQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+;

int s[N],ed_cnt,head[N],n,m,f[N][N],as;

bool vis[N][N][];

struct ed{int to,nxt;}edge[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri fr,ri to){edge[++ed_cnt]=(ed){to,head[fr]};head[fr]=ed_cnt;}

il void solve(ri x){e(i,x){solve(t(i));my(j,m+,)rp(k,,j-)f[x][j]=max(f[x][j],f[t(i)][k]+f[x][j-k]);}}

int main()

{

    freopen("2014.in","r",stdin);freopen("2014.out","w",stdout);

    n=read();m=read();

    rp(i,,n)ad(read(),i),f[i][]=read();

    solve();printf("%d\n",f[][m+]);

    return ;

}

[ ]$Accumulation\ Degree$

写这儿辣

[X]$Naptime$

做过了,看这儿

[X]环路运输

考虑先断环为链并日常长度×2?

然后考虑这道题变成了什么样儿?就,求$max(A_{i}+A_{j}+i-j)$,其中$i\leq 2\cdot n,j\leq 2\cdot n,i-j\leq \frac{n}{2}$

考虑枚举$i$,然后现在就是要求$max(A_{j}-j)$,显然考虑单调队列?

这样儿复杂度均摊下来就差不多是$O(n)$的,$over$

话说这真的是个$dp$,,,?

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=1e6+;

int n,a[N<<],que[N<<],head,tail,as;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

struct gdgs

{

    int que[N<<],head,tail;

    gdgs(){head=,tail=;}

    il int top(){return a[que[head]]-que[head];}

    il void push(ri x){while(a[que[tail]]-que[tail]<=a[x]-x && tail>=head)--tail;que[++tail]=x;}

    il void clr(ri x){while(que[head]<x && tail>=head)++head;}

}qwq;

int main()

{

    //freopen("5501.in","r",stdin);freopen("5501.out","w",stdout);

    n=read();rp(i,,n)a[i]=a[i+n]=read();

    rp(i,,n<<)

    {

        qwq.clr(i-n/);

        if(i>=n)as=max(as,a[i]+i+qwq.top());qwq.push(i);

    }

    printf("%d\n",as);

    return ;

}

[X]$Broken\ Robot$

做过了,看这儿

[X]$Mondriaan's\ Dream$

做过了,看这儿

[X]炮兵阵地

做过了,看这儿

[X]开车旅行

很久以前就想做了,,,然后一直没做嘤嘤嘤

考虑预处理出从每个城市$i$出发,小$A$和小$B$分别会去的第一个城市,记为$nxta_{i}$和$nxtb_{i}$

然后考虑再设个$f_{i,j,0/1}$表示从$i$出发,经过$2^{j}$个城市,从小A/小B开始最终到的城市,$l_{a/b,i,j,0/1}$表示路程

显然瞎倍增转移下就好,,,

然后后面也瞎倍增下就做完辣,,

$over$

昂然后首先第一个难点就在预处理,,,这儿有三个方法,一个是用$set$,一个是用双向链表,还一个是用$splay$.因为挺久没练$splay$了,所以估计我之后放的$code$会是$set$版本的,,,?但这两种方法还是都会港下的$QwQ$

首先港下$set$的趴$QwQ$,考虑从后往前加入$set$,顺便把每个点的后边的最近和次近的点就能直接找到了,$over$

双向链表的思路比较类似,但感觉复杂度也许好看些,,,?感觉而已$QwQ$大致思路是先排序,然后考虑从前往后找,显然对第一个点来说所有点都在它后边,于是就能很轻松地找到第一个点的$nxt$,然后就把第一个点删了,这样第二个点就变成第一个点了,这么做下去就好鸭$QwQ$

$splay$其实也差不多鸭$QwQ$和$set$一样儿的思想,然后直接查询$pre$和$nxt$就好$QwQ$

$umm$倍增还是详细点儿港趴,,,

首先还是解释下那几个预处理的数组的意思_(:з」∠)_

其实$f$是比较好解释的$QwQ$?$f_{i,j,0}$指小$a$走第一步,以$i$为起点,走$2^{j}$到达的城市.$f_{i,j,1}$指小$b$走第一步

然后这个$l$我大概港下$QwQ$,其实也还是挺好解释的来着$QwQ$.$l_{a,i,j,0}$指小$a$走第一步,以$i$为起点,走$2^{j}$,小$a$走的路程.$l_{a,i,j,1}$指小$a$走第一步,小$b$走的路程.$l_{b,i,j,0}$指小$b$走第一步,小$a$走的路程,$l_{b,i,j,1}$指小$b$走第一步,小$b$走的路程

变量有点儿多但思路还是挺顺的嘛$QwQ$

然后瞎转移就成$QwQ$,另外,记得特判边界昂$QwQ$

还有一个小细节,是在转移的时候,不难发现,因为$2^{i}$为偶数,所以从谁出发的走了$2^{i}$之后依然是从谁出发.但这儿有个细节,就当$i=1$的时候,因为它实际上是拆成$2^{i-1}$和$2^{i-1}$,就会导致出现奇数,也就是说变为从谁出发转移中就变为另一个人出发,所以对$i=1$要提前处理掉,不能一块儿做昂$QwQ$

真·over?

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define lf double

#define int long long

#define gc getchar()

#define mp make_pair

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=+,inf=1e9+;const lf eps=1e-;

int n,h[N],f[N][][],la[N][][],lb[N][][],as1,as2,as;

lf tmp_as;

il int read()

{

    ri x=;rb y=;rc ch=gc;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

namespace gdgs

{

    int rt,nod_cnt;

    struct node{int fa,ch[],val,cnt,sz,nam;il void pre(ri x,ri fat,ri name){ch[]=ch[]=;fa=fat;val=x;cnt=sz=;nam=name;}}tr[N];

    struct qwq{int nam,hei;}qaq[];

    il int abs(ri x){return x>?x:-x;}

    il bool cmp(qwq gd,qwq gs){return abs(gd.hei)==abs(gs.hei)?gd.hei<gs.hei:abs(gd.hei)<abs(gs.hei);}

    il void pushup(ri x){tr[x].sz=tr[tr[x].ch[]].sz+tr[tr[x].ch[]].sz+tr[x].cnt;}

    il void rotate(ri x)

    {

        ri fa=tr[x].fa,grdfa=tr[fa].fa;bool op1=tr[fa].ch[]==x,op2=tr[grdfa].ch[]==fa;

        tr[grdfa].ch[op2]=x;tr[x].fa=grdfa;

        tr[fa].ch[op1]=tr[x].ch[op1^];tr[tr[x].ch[op1^]].fa=fa;

        tr[fa].fa=x;tr[x].ch[op1^]=fa;

        pushup(fa);pushup(x);

    }

    il void splay(ri x,ri goal)

    {

        while(tr[x].fa!=goal)

        {

            ri fa=tr[x].fa,grdfa=tr[fa].fa;

            if(grdfa!=goal)(tr[fa].ch[]==x)^(tr[grdfa].ch[]==fa)?rotate(x):rotate(fa);

            rotate(x);

        }

        if(!goal)rt=x;

    }

    il void insert(ri x,ri nam)

    {

        ri nw=rt,fa=;

        while(nw && tr[nw].val!=x)fa=nw,nw=tr[nw].ch[x>tr[nw].val];

        nw=++nod_cnt;if(fa)tr[fa].ch[x>tr[fa].val]=nod_cnt;tr[nod_cnt].pre(x,fa,nam);

        splay(nw,);

    }

    il void fd(ri x){ri nw=rt;if(!nw)return;while(tr[nw].ch[x>tr[nw].val] && x!=tr[nw].val)nw=tr[nw].ch[x>tr[nw].val];splay(nw,);}

    il int ask_pr(ri x){fd(x);ri nw=tr[rt].ch[];while(tr[nw].ch[])nw=tr[nw].ch[];return nw;}

    il int ask_nxt(ri x){fd(x);ri nw=tr[rt].ch[];while(tr[nw].ch[])nw=tr[nw].ch[];return nw;}

    il void pre_nxt()

    {

        insert(inf,);insert(inf+,);insert(-inf,);insert(-inf-,);f[n-][][]=n;lb[n-][][]=abs(h[n]-h[n-]);insert(h[n],n);insert(h[n-],n-);

        my(i,n-,)

        {

            insert(h[i],i);

            qaq[].nam=tr[ask_pr(h[i])].nam,qaq[].hei=h[qaq[].nam]-h[i];

            qaq[].nam=tr[ask_pr(h[qaq[].nam])].nam;qaq[].hei=h[qaq[].nam]-h[i];

            qaq[].nam=tr[ask_nxt(h[i])].nam,qaq[].hei=h[qaq[].nam]-h[i];

            qaq[].nam=tr[ask_nxt(h[qaq[].nam])].nam;qaq[].hei=h[qaq[].nam]-h[i];

            sort(qaq+,qaq++,cmp);

            f[i][][]=qaq[].nam;f[i][][]=qaq[].nam;lb[i][][]=abs(qaq[].hei);la[i][][]=abs(qaq[].hei);

        }

    }

}

il void pre()

{

    rp(i,,n)

    {

        f[i][][]=f[f[i][][]][][];f[i][][]=f[f[i][][]][][];

        if(f[i][][])la[i][][]=la[i][][],la[i][][]=lb[f[i][][]][][];

        if(f[i][][])lb[i][][]=lb[i][][],lb[i][][]=la[f[i][][]][][];

    }

    for(ri j=;((<<j)|)<=n;++j)

        rp(i,,n-(<<j))

        {

            f[i][j][]=f[f[i][j-][]][j-][];f[i][j][]=f[f[i][j-][]][j-][];

            if(f[i][j][])la[i][j][]=la[i][j-][]+la[f[i][j-][]][j-][],la[i][j][]=la[i][j-][]+la[f[i][j-][]][j-][];

            if(f[i][j][])lb[i][j][]=lb[i][j-][]+lb[f[i][j-][]][j-][],lb[i][j][]=lb[i][j-][]+lb[f[i][j-][]][j-][];

        }

}

il void query(ri x,ri dis,ri &as1,ri &as2,rb y)

{

    //printf("x=%d dis=%d as1=%d as2=%d y=%d\n",x,dis,as1,as2,y);

    if(!y)

    {

        my(i,,)

            if(f[x][i][] && la[x][i][]+la[x][i][]<=dis)

            {dis-=la[x][i][]+la[x][i][];as1+=la[x][i][];as2+=la[x][i][];/*printf("  i=%d\n",i);*/query(f[x][i][],dis,as1,as2,y^(i==));return;}

    }

    else

    {

        my(i,,)

            if(f[x][i][] && lb[x][i][]+lb[x][i][]<=dis)

            {dis-=lb[x][i][]+lb[x][i][];as1+=lb[x][i][];as2+=lb[x][i][];/*printf("  i=%d\n",i);*/query(f[x][i][],dis,as1,as2,y^(i==));return;}

    }

}

 main()

{

    //freopen("1081.in","r",stdin);freopen("1081.out","w",stdout);

    n=read();rp(i,,n)h[i]=read();h[]=inf;gdgs::pre_nxt();pre();

    //rp(j,0,3)rp(i,1,n)printf("(%d,%d) a:f=%d la=%d lb=%d b:f=%d la=%d lb=%d\n",i,j,f[i][j][0],la[i][j][0],la[i][j][1],f[i][j][1],lb[i][j][0],lb[i][j][1]);

    /*预处理麻油问题!yep!*/

    ri x=read();tmp_as=inf;

    rp(i,,n)

    {

        ri as1=,as2=;lf tmp;query(i,x,as1,as2,);

        //printf("i=%d as1=%d as2=%d\n",i,as1,as2);

        if(!as2)continue;

        tmp=(lf)as1/as2;

        if(tmp_as>tmp)tmp_as=tmp,as=i;

        else if(abs(tmp_as-tmp)<=eps && h[i]>h[as])as=i;

    }

    printf("%lld\n",as);

    ri m=read();

    while(m--){ri s=read(),x=read(),as1=,as2=;query(s,x,as1,as2,);printf("%lld %lld\n",as1,as2);}

    return ;

}

[X]$Count\ The\ Repetitions$

感觉这题长得很像做过的样子,,,但找了半天就是没找到是为什么嘤嘤嘤

$umm$有人不能发现$conn(conn(s_2,n_2 ),m)$就是$conn(s_{2},n_2\cdot m)$嘛,,,?

所以可以考虑先求出一个$ {m}' $表示$ conn ( s_{2} , {m}' ) $不能用$ conn(s_{1} , n_{1}) $生成,然后直接就能求出$m$辣$QwQ$

欧克现在就考虑怎么求这个${m}'$,因为打起来挺麻烦我后面就都用$m$表示辣,,,也就说后面所有$m$表示的都${m}'$昂$QwQ$

然后因为后文中的$n_{2}$也就完全麻油意义辣,所以后文所有$n_{1}$都写成$n$,也就说$后面所有n$表示的都$n_{1}$鸭$QwQ$

然后现在发现$m$可能很大,上界是$\frac{|s_{1}|\cdot n_{1}}{|s_{2}|}$,于是考虑先二进制拆分掉,就,假如$m=2^{p_{1}}+2^{p_{2}}+2^{p_{3}}+...$,就可以当做$conn(s_{2},m)$是由$conn(s_{2},2^{p_{1}}),conn(s_{2},2^{p_{2}}),...$拼起来这样儿的

然后还有一个是$n$也挺大的吼,这里可以先假设$n$足够大,即$s_{1}$重复了无数次

然后考虑设$f_{i,j}$表示从$s_{1}[i]$开始,能生成$conn(s_{2},2^{j})$的最少字符数

显然转移有$f_{i,j}=f_{i,j-1}+f_{(i+f_{i,j-1})\ mod\ |s_{1}|,j-1}$

十分显然懒得解释了,,,

然后瞎预处理一通就欧克$QwQ$

然后最后求答案同样瞎搞一通($bushi$就做完辣,,,

$over$
#include<bits/stdc++.h>

using namespace std;

#define il inline

#define int long long

#define lf double

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=+;

int n,f[N][],tot_len,len1,len2,m;

char s1[N],s2[N];

il int read()

{

    ri x=;rb y=;rc ch=gc;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool pre()

{

    rp(i,,len1-)

    {ri pos=i;rp(j,,len2-){ri cnt=;while(s1[pos]!=s2[j]){++pos;pos%=len1;++cnt;if(cnt>len1)return printf("0\n"),;}++pos;pos%=len1;f[i][]+=cnt+;}}

    rp(j,,)rp(i,,len1-)f[i][j]=f[i][j-]+f[(i+f[i][j-])%len1][j-];

    return ;

}

 main()

{

    while(~scanf("%s",s2))

    {

        memset(f,,sizeof(f));

        ri n2=read();scanf("%s",s1);n=read();len1=strlen(s1);len2=strlen(s2);tot_len=len1*n;m=;

        if(!pre())continue;ri pos=;my(i,,)if(f[pos][i]<=tot_len){/*printf("tot_len=%d f[%d][%d]=%d\n",tot_len,pos,i,f[pos][i]);*/tot_len-=f[pos][i],m+=<<i,pos+=f[pos][i],pos%=len1;}

        printf("%lld\n",m/n2);

    }

    return ;

}

[ ]$Cleaning\ Shifts$

无脑$dp$,只是要数据结构优化下

话说我还没做过数据结构优化$dp$的题目,,,只听说过,,,所以还挺新奇的嘿$QwQ$

首先显然考虑无脑$dp$怎么搞?

就$f_{i}$表示搞到$i$了的最小代价

转移就$f_{r_{i}}=(f_{x})_{min}+c_{i}$,其中$x\in [l_{i}-1,r_{i]}$

区间最值这种不显然线段树维护就好,,,?

$over$

哦然后一个$attention$,就,这题还挺友好的,坐标范围很小,就直接做就好,否则是要离散化的昂$QwQ

口胡完感$jio$很$easy$的亚子,咕了,$QwQ$

[X]$The\ Battle\ of\ Chibi$

先不考虑数据范围,思考怎么做

设$f_{i,j}$表示以$i$结尾长度为$j$的最长上升子序列个数

转移显然就$f_{i,j}=\sum f_{k,j-1},a_{k}<a_{i}$

然后考虑转移顺序?就$j$在外层$i$在内层.

然后现在的问题在于,数据范围比较大,如果枚举$k$显然会超时$kk$

所以现在就是要优化这个计算$k$的过程

考虑因为$j$在外层,可以先当作$j$是定值,就有$f_{i}=\sum f_{k},a_{k}<a_{i}$

不难想到树状数组?

于是就树状数组优化下就做完了$QwQ$

还有个就,$a_{i}$的范围挺大的,记得离散化昂

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define int long long

#define lf double

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define lowbit(x) (x&(-x))

#define lb(x) lower_bound(st+1,st+1+st_cnt,x)-st

const int N=+,mod=1e9+;

int n,m,a[N],f[N][N],st[N],st_cnt,cnt,tr[N];

il int read()

{

    ri x=;rb y=;rc ch=gc;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri x,ri dat){while(x<=st_cnt)tr[x]=(tr[x]+dat)%mod,x+=lowbit(x);}

il int query(ri x){ri ret=;while(x){ret=(ret+tr[x])%mod;x-=lowbit(x);}return ret;}

 main()

{

    ri T=read();

    while(T--)

    {

        printf("Case #%lld: ",++cnt);memset(f,,sizeof(f));

        n=read();m=read();rp(i,,n)a[i]=st[i]=read();sort(st+,st++n);st_cnt=unique(st+,st++n)-st-;rp(i,,n)a[i]=lb(a[i]),f[i][]=;

        rp(j,,m){memset(tr,,sizeof(tr));rp(i,,n)f[i][j]=query(a[i]-),ad(a[i],f[i][j-]);}

        ri as=;rp(i,,n)as=(as+f[i][m])%mod;printf("%lld\n",as);

    }

    return ;

}

[X]$Fence$

做过了,看这儿

[ ]$cut\ the\ sequence$

咕了,下午写$QAQ$

[ ]任务安排

写这儿辣

[ ]任务安排2

写这儿辣

[ ]任务安排3

太菜了不会斜率优化,咕了

[X]$cats\ trandsport$

写这儿辣

[ ]诗人小$G$

神奇四边形不等式在哪里?

不会,咕了

欢迎催更$QwQ$

反正我也不会写的($bushi$

[ ]再探石子合并

$umm$就数据范围++

于是用个四边形不等式就好

然而我不会

所以会详细写的$QwQ$

[ ]$Gerald\ and\ Giant\ Chess$

本来是可以无脑$dp$的,,,

但是数据范围太大辣$kk$,考虑转化这道题

不难发现,如果没有黑色格子,从左上到右下的方案一个组合数就出来辣$QwQ$

然后就只要求出从左上到右下至少经过一个黑色棋子的方案了$QwQ$

考虑设$f_{i}$表示从左上角走到第$i$个黑色棋子的方案数,用组合数+容斥瞎转移下就好,,,

$over$

[ ]$Connected\ Graph$

写这儿辣

[ ]$hwo\ many\ of\ them?$

挺神的我$jio$得,,,没看书上题解我真没想到$kk$

考虑设$f_{i,j}$表示$i$个点构成的包含$j$条割边的无向连通图数量

然后计数类$dp$呢,有个基本思想,是这样儿的,下课了咕了下午写$QAQ$

[X]$A\ Decorative\ Fence$

写这儿辣

[X]乌龟棋

无脑$dp$

考虑设$f_{i,j,k,p,q}$表示每张牌剩余的数量

$over$

很久以前的$code$了,贼丑$QAQ$

#include<bits/stdc++.h>

using namespace std;

int n,m,s[],c[],dp[][][][];

bool o;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)cin>>s[i];

    for(int i=;i<=m;i++)

    {

        int t;

        cin>>t;

        c[t]++;

    }

    dp[][][][]=s[];

    for(int i=;i<=c[];i++)

        for(int j=;j<=c[];j++)

            for(int k=;k<=c[];k++)

                for(int p=;p<=c[];p++)

                {

                    if(i>)dp[i][j][k][p]=max(dp[i-][j][k][p]+s[i+j*+k*+p*+],dp[i][j][k][p]);

                    if(j>)dp[i][j][k][p]=max(dp[i][j-][k][p]+s[i+j*+k*+p*+],dp[i][j][k][p]);

                    if(k>)dp[i][j][k][p]=max(dp[i][j][k-][p]+s[i+j*+k*+p*+],dp[i][j][k][p]);

                    if(p>)dp[i][j][k][p]=max(dp[i][j][k][p-]+s[i+j*+k*+p*+],dp[i][j][k][p]);

//                    cout<<"i="<<i<<" j="<<j<<" k="<<k<<" p="<<p<<" dp="<<dp[i][j][k][p]<<endl;

                }

    cout<<dp[c[]][c[]][c[]][c[]];

    return ;

}

[X]花店橱窗

无脑$dp$

甚至连题解都不想写

直接看$code$趴,,,

#include<bits/stdc++.h>

using namespace std;

long long a[],n,i,j,k,ans[][],maxans;

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

        a[i+n]=a[i];

    }

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

        for(j=i-;j>= && i-j<n;j--)

        {

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

                ans[j][i]=max(ans[j][i],ans[j][k]+ans[k+][i]+a[i+]*a[k+]*a[j]);

            maxans=max(maxans,ans[j][i]);

        }

    cout<<maxans;

    return ;

}

[ ]$Buy\ Low\ Buy\ Lower$

[ ]$Trip$

[ ]$Substract$

[ ]陨石的秘密

[ ]划分大理石

[ ]$Folding$

[X]能量项链

无脑区间$dp$,瞎搞下就好,,,?

懒得写了入门题没什么可写的昂$QAQ$

很久以前的代码,丑,没了

#include<bits/stdc++.h>

using namespace std;

long long a[],n,i,j,k,ans[][],maxans;

int main()

{

    cin>>n;

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

    {

        cin>>a[i];

        a[i+n]=a[i];

    }

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

        for(j=i-;j>= && i-j<n;j--)

        {

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

                ans[j][i]=max(ans[j][i],ans[j][k]+ans[k+][i]+a[i+]*a[k+]*a[j]);

            maxans=max(maxans,ans[j][i]);

        }

    cout<<maxans;

    return ;

}

[ ]棋盘分割

[X]$Blocks$

叶佬在$NOIp$的时候讲过,所以那时候就落实了$QwQ$

显然区间$dp$?就设$f_{l,r,k}$,表示的$[l,r]$这个颜色区间,然后右侧还有$k$个和$col_{j}$颜色相同的格子的最大贡献(为什么还会有这个$k$呢,挺显然的还$QwQ$,就因为可能有一段中间被消了之后就会出现拖家带口($bushi$)这种情况辣$QwQ$

好像解释得不太清,,,不管了懒得解释了$QAQ$,如果有没$get$的在下面留言下啥的我再重新港下,,,$QAQ$

#include<algorithm>

#include<iomanip>

#include<cstring>

#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,l,r) for(ri i=l;i<=r;++i)

#define my(i,l,r) for(ri i=l;i>=r;--i)

const int N=;

int n,color[N],cnt[N],f[N][N][N],now,ct,ans;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

int bfs(int l,int r,int k)

{

    if(f[l][r][k]!=)return f[l][r][k];if(l>r)return ;

    f[l][r][k]=bfs(l,r-,)+(cnt[r]+k)*(cnt[r]+k);

    rp(i,l,r-)if(color[i]==color[r])f[l][r][k]=max(bfs(l,i,cnt[r]+k)+bfs(i+,r-,),f[l][r][k]);

    return f[l][r][k];

}

int main()

{

//    freopen("QAQ.in","r",stdin);freopen("QAQ.out","w",stdout);

    ri T=read();

    rp(i,,T)

    {

        memset(color,,sizeof(color));memset(f,,sizeof(f));now=;n=read();

        rp(j,,n){ct=read();if(ct==color[now])++cnt[now];else{++now;cnt[now]=;color[now]=ct;}}

        ans=bfs(,now,);

        cout<<"Case "<<i<<": "<<ans<<endl;

    }

    return ;

}

[ ]$Strategic\ game$

[ ]$Bugs\ Integrated\ Inc$

[ ]$Fence\ Obstacle\ Course$

[ ]$K-Anonymous\ Sequence$

[ ]$Post\ Office$

[ ]扑克牌

[ ]$The\ Counting\ Problem$

随机推荐

CSharp数据库代码生成工具
项目中遇到很多数据库表字段特别多的项目,手动一个一个去敲也不知道敲到什么时候,突发奇想做一个工具一劳永逸.花了一晚上做了这个东西,代码写的比较乱,用这个工具后减少了很多时间. Git地址:https: ...
sap 中怎样把非限制库存转为销售订单库存？
把非限制库存转为销售订单库存: MB1B 移动类型413 把销售订单库存转为非限制库存: MB1B移动类型411 E 切记!
Linux ALSA声卡驱动之三：PCM设备的创建
声明:本博内容均由http://blog.csdn.net/droidphone原创,转载请注明出处,谢谢! 1. PCM是什么模数转换模拟信号经过pcm(脉冲编码调制)后为pcm数据: PCM是 ...
Postman入门使用
Postman 是一个很强大的 API调试.Http请求的工具,方便易用,毋庸置疑. 1.Postman安装 a. 打开谷歌浏览器 b. 进入设置界面 c. 选择扩展程序 d. 选择chrome网上应 ...
关于最近996&period;icu的一点感想
最近这个996.ICU的话题讨论的火热,特别是一些业界大佬有直言不讳的说就是要996,有的弄些鸡汤文把996说成年轻人就该这样的.作为一个普通的码农,实在是看不下去了,在这里说些自己的看法,希望年轻人 ...
linux 的内核的作用和功能
Linux内核[kernel]是整个操作系统的最底层, 它负责整个硬件的驱动,以及提供各种系统所需的核心功能, 包括防火墙机制.是否支持LVM或Quota等文件系统等等, 如果内核不认识某个最新的硬件 ...
HDCMS留言插件的使用！
HDCMS留言插件,JS简单示例: <img src='{|U:'code'}' onclick='this.src='{|U:'code'}&'+Math.random()' /&gt ...
iOS开发之 -- bundle程序束的制造
我们在写项目的时候,需要添加大量的图片,这个时候除了在x-code-->Assets文件里面添加图片外,还可以添加程序束,这样的话项目看起来比较整齐,也显得比较专业,下面就来说一下程序束的制造 ...
Netty组件介绍（转）
http://www.tuicool.com/articles/mEJvYb 为了更好的理解和进一步深入Netty,我们先总体认识一下Netty用到的组件及它们在整个Netty架构中是怎么协调工作的. ...
myeclipse保存时弹出Building workspace
最近做项目,每次保存修改的东西.myeclipse都会building workspace(重新编译)一下.并且那 building的速度真不够慢的啊. 严重影响编程速度. 在网上也发现遇到此问题的很 ...

码农公寓

[X]$Mr.Young's\ Picture\ Permutations$

[X]$LCIS$

[X]$Mobile\ Service$

[X]$Making\ the\ Grade$

[X]传纸条

[X]$I-country$

[X]$Cookies$

[X]数字组合

[X]自然数拆分

[X]$Jury\ Compromise$

[X]$Coins$

[X]石子合并

[X]$Polygon$

[X]金字塔

[X]没有上司的舞会

[X]选课

[ ]$Accumulation\ Degree$

[X]$Naptime$

[X]环路运输

[X]$Broken\ Robot$

[X]$Mondriaan's\ Dream$

[X]炮兵阵地

[X]开车旅行

[X]$Count\ The\ Repetitions$

[ ]$Cleaning\ Shifts$

[X]$The\ Battle\ of\ Chibi$

[X]$Fence$

[ ]$cut\ the\ sequence$

[ ]任务安排

[ ]任务安排2

[ ]任务安排3

[X]$cats\ trandsport$

[ ]诗人小$G$

[ ]再探石子合并

[ ]$Gerald\ and\ Giant\ Chess$

[ ]$Connected\ Graph$

[ ]$hwo\ many\ of\ them?$

[X]$A\ Decorative\ Fence$

[X]乌龟棋

[X]花店橱窗

[ ]$Buy\ Low\ Buy\ Lower$

[ ]$Trip$

[ ]$Substract$

[ ]陨石的秘密

[ ]划分大理石

[ ]$Folding$

[X]能量项链

[ ]棋盘分割

[X]$Blocks$

[ ]$Strategic\ game$

[ ]$Bugs\ Integrated\ Inc$

[ ]$Fence\ Obstacle\ Course$

[ ]$K-Anonymous\ Sequence$

[ ]$Post\ Office$

[ ]扑克牌

[ ]$The\ Counting\ Problem$

随机推荐

相关文章