期望得分：100+30+60=190

实际得分：10+0+55=65

 

到了233 2是奇数位 或223 第2个2是偶数位就会223 、233 循环

#include
      
       #define N 1000001using namespace std;char s[N+5];int main(){    freopen("trans.in","r",stdin);    freopen("trans.out","w",stdout);    int n,k; bool ok;    while(scanf("%d%d",&n,&k)!=EOF)    {        scanf("%s",s+1);        ok=false;        for(int i=1;i
      

 

 

 

注：不能向上走

 

因为蛇可以在一行内任意移动

他最终在一行内的移动范围是一段连续的区间

所以本题可以用区间DP解决

 

f[i][j][k] 表示 前i行，长度为j，从第k列离开第i行的最大得分

g[j][l][r] 表示当前长度为j，在区间[l,r]内移动，没有死亡的最大得分

开始时 ，对于每一个i，f[i][j][k]=g[j][k][k]=f[i-1][g-a[i][k]][k]+max(-a[i][k],0)

然后，区间由内向外更新， g[j][l][r]=max(g[j-a[i][l]][l+1][r]+a[i][l],g[j-a[i][r]][l][r-1]+a[i][r])

最后 更新f f[i][j][k]=max(g[j][l][r]) k∈[l,r]

#include
      
       #include
       
        #include
        
         #include
         
          #define N 201using namespace std;int a[N][6];int f[N][N*10][6],g[N*10][6][6];bool can[N][6];void read(int &x){    x=0; int f=1; char c=getchar();    while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }    x*=f;}int main(){    freopen("snakevsblock.in","r",stdin);    freopen("snakevsblock.out","w",stdout);    int n,sum=4;    read(n);    for(int i=1;i<=n;i++)        for(int j=1;j<=5;j++)        {            read(a[i][j]);            if(a[i][j]>0) sum+=a[i][j];         }    int m,x,y;    read(m);     for(int i=1;i<=m;i++)    {        read(x); read(y);        can[x][y]=true;    }    memset(f,-127,sizeof(f));    f[0][4][3]=0;    int r;    for(int i=1;i<=n;i++)    {        memset(g,-127,sizeof(g));        for(int j=0;j<=sum;j++)             for(int k=1;k<=5;k++)                if(j-a[i][k]>=0) f[i][j][k]=g[j][k][k]=f[i-1][j-a[i][k]][k]+max(-a[i][k],0);        for(int len=2;len<=5;len++)            for(int l=1;l+len-1<=5;l++)                for(int j=0;j<=sum;j++)                {                    r=l+len-1;                    if(!can[i][l] && j-a[i][l]>=0) g[j][l][r]=g[j-a[i][l]][l+1][r]+max(-a[i][l],0);                    if(!can[i][r-1] && j-a[i][r]>=0) g[j][l][r]=max(g[j][l][r],g[j-a[i][r]][l][r-1]+max(-a[i][r],0));                    for(int k=l;k<=r;k++) f[i][j][k]=max(f[i][j][k],g[j][l][r]);                }    }    int ans=0;    for(int i=1;i<=n;i++)        for(int j=0;j<=sum;j++)            for(int k=1;k<=5;k++)                ans=max(ans,f[i][j][k]);    printf("%d",ans);        }
         
        
       
      

 

 

 

前 30%： O（2^n * n^3）

暴力枚举哪些站点损坏，floyd判断这些站点损坏时，测试的站点是否连通 

 另20%：O（nlogn+k）

问题转化为选择最少的点覆盖所有的线段

即留下最多的区间，使区间不相交

按右端点从小到大排序 ，删掉与当前区间有交的区间

另10%：分类讨论即可

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define N 100001int n,m,k,out=1e6;int front[N],nxt[N<<1],to[N<<1],tot;int in[N],ans[N],id[N],cnt;int cut[N][2];bool con[16][16],f[16];int E[N][2];int vis[N],fa[N][18];struct node{    int l,r,nl,nr;}e[N*3];queue
           
            q;void read(int &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v){ to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;}bool cmp(node p,node q){ return p.nr
            
             e[i].nr) swap(e[i].l,e[i].r),swap(e[i].nl,e[i].nr); } sort(e+1,e+k+1,cmp); int sum=0,last=0; for(int i=1;i<=k;i++) if(e[i].nl>last) last=e[i].nr,ans[++sum]=e[i].r; printf("%d\n",sum); for(int i=1;i<=sum;i++) printf("%d ",ans[i]);}void judge(int sum){ memset(con,false,sizeof(con)); for(int i=1;i<=n;i++) if(!f[i]) con[i][i]=true; for(int i=1;i<=m;i++) if(!f[E[i][0]] && !f[E[i][1]]) con[E[i][0]][E[i][1]]=con[E[i][1]][E[i][0]]=true; for(int h=1;h<=n;h++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(h!=i && h!=j && i!=j && con[i][h] && con[h][j]) con[i][j]=true; for(int i=1;i<=k;i++) if(con[cut[i][0]][cut[i][1]]) return; if(sum
             
              =out) return; if(now==n+1) { judge(sum); return; } dfs(now+1,sum); f[now]=true; dfs(now+1,sum+1); f[now]=false;}void solve1(){ read(k); for(int i=1;i<=k;i++) read(cut[i][0]),read(cut[i][1]); dfs(1,0); printf("%d\n",out); for(int i=1;i<=out;i++) printf("%d ",ans[i]);}void dfs2(int x,int y){ id[x]=++tot; for(int i=front[x];i;i=nxt[i]) if(to[i]!=y) fa[to[i]][0]=x,dfs2(to[i],x);}int getlca(int u,int v){ if(u==v) return u; if(id[u]
              
               =0;i--) if(id[fa[u][i]]>id[v]) u=fa[u][i]; return fa[u][0];}void solve3(){ tot=0; dfs2(1,0); for(int j=1;j<=17;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; read(k); int u,v,lca; for(int i=0;i
              
             
            
           
          
         
        
       
      

 

满分做法：

将链上的做法搬到树上

对所有的询问，按他们的lca排序

然后从下到上处理树上的节点，若以当前节点为lca的测试站点还连通，就把当前节点破坏

dfs序+树链剖分维护即可

#include
      
       #include
       
        #include
        
         using namespace std;#define N 100001int n,m,p;int cut[N*3][2],lca[N*3];int siz[N],fa[N][18];int cnt,id[N],bl[N];int q[N*3],lr[N][2];bool f[N<<2];int ans[N];int front[N],nxt[N<<1],to[N<<1],tot;void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;}void init(){    read(n); read(m);    int u,v;    for(int i=1;i<=m;i++)     {        read(u); read(v);        add(u,v);    }    read(p);    for(int i=1;i<=p;i++) read(cut[i][0]),read(cut[i][1]);}void dfs1(int x,int y){    fa[x][0]=y; siz[x]=1;    for(int i=front[x];i;i=nxt[i])        if(to[i]!=y) dfs1(to[i],x),siz[x]+=siz[to[i]];}void dfs2(int x,int top){    id[x]=++cnt;    bl[x]=top;    int y=0;    for(int i=front[x];i;i=nxt[i])        if(to[i]!=fa[x][0] && siz[to[i]]>siz[y]) y=to[i];    if(!y) return;    dfs2(y,top);    for(int i=front[x];i;i=nxt[i])        if(to[i]!=fa[x][0] && to[i]!=y) dfs2(to[i],to[i]); }void prelca(){    for(int i=1;i<=17;i++)        for(int j=1;j<=n;j++)            fa[j][i]=fa[fa[j][i-1]][i-1];}int getlca(int u,int v){    if(u==v) return u;    if(id[u]
         
          =0;i--)        if(id[fa[u][i]]>id[v]) u=fa[u][i];    return fa[u][0];}bool cmp(int a,int b){    return lca[a]
          
           >1;    if(pos<=mid) modify(k<<1,l,mid,pos);    else modify(k<<1|1,mid+1,r,pos);}bool query(int k,int l,int r,int opl,int opr){    if(l==opl && r==opr) return f[k];    int mid=l+r>>1;    if(opr<=mid) return query(k<<1,l,mid,opl,opr);    if(opl>mid) return query(k<<1|1,mid+1,r,opl,opr);    return query(k<<1,l,mid,opl,mid)|query(k<<1|1,mid+1,r,mid+1,opr); }bool QUERY(int u,int v){    while(bl[u]!=bl[v])    {        if(id[u]