7.26 Dp 主题赛 赛后总结

T1

T1看上去就很板，开场后有几个人一直在说话导致我心烦意乱，加上 Sorato 和 Psm 很快就切掉，可我确一直没有思路，所以开始的时候很慌。后来冷静下来仔细思考一下，首先注意到数据范围允许\(O(n^2)\)的dp，不难想到设置一个这样的dp状态，\(f[i]\)表示将区间\([1,i]\)变成美丽的所需的最小花费，那么有一个很显然的dp转移方程：\(f[i]=min(f[i],f[j-1]+ask(j,i))\) ，其中\(ask(j,i)\)表示把该区间变成偶回文的所需的花费。考虑 枚举 i,j 需要两重循环，这就要求我们用 \(O(logn)\)甚至是\(O(1)\)的复杂度来得到 \(ask(j,i)\)的值。赛时由于心态问题，考虑到这一步就卡住了，注意到这个值很显然可以 \(O(n^2)\)预处理出来，所以本题得到解决。

这启示我们在遇到某些值不好暴力处理的时候，不妨考虑能否预处理，或者数据结构优化一下？

T2

T2是一道博弈dp，首先码了一个dfs交上去30，调成记忆化之后变成50了，实际上记忆化就是正解，但可能是由于数据问题莫名其妙一直RE，必须开到远大于给定数据范围的值才能通过，赛时最后还是A了，但还是因为一些场外因素耽误了很多时间。

T3

T3有点智慧，赛时码了一个dfs交上去，拿了5分，我看大多数都是30，35，还以为暴搜码炸了，调那个暴搜调到死，最后告诉我，暴搜就是5分。fyx把暴搜换成bfs得了50，所以以后还是码bfs吧。

T3比较智慧的地方在于一步转化：考虑对于当前的字符串s，枚举所有情况，判断是否能在k步之内实现。那么就有两个问题，1.情况总数是多少？答案是一个组合数级别的：\(C_n^a*C_{n-a}^b\)，也就是n的阶乘除以a,b,c,阶乘的乘积。第二个问题，如何判断能否实现呢？考虑一个这样的贪心：对于一个字符ch，设它在s中出现的第x次对应的位置为u，在枚举出的串第x次出现的位置为v，那么显然是把u换到v最优。我们把新字符串上的每个位置令赋一个值表示此位置对应在原串的位置，那么答案即为逆序对个数。考虑优化这个算法，既然是dp题，又注意到字符串只有：'K','E','Y'这三个字符，加上本题对于步数的限制，所以设置\(f[i][j][k][t]\)表示当前新串已经使用了\(i+j+k\)个位置，使用了 i个K,j 个E,k 个Y ，且 一共换了 t次，的方案数。显然可以\(O(1)\)转移，于是本题得到解决。

T4

这道题出的很没意思，把暴力加个记忆化就A了，难点在于如何暴力？赛时想码暴力的部分分确实不会。

这个方法应该是可复制的，可以记录一下，把起点，终点，墙，锤子都用一个结构体类型的变量来存储，暴搜时暴力向两边拓展即可。加个记忆化复杂度就来到了\(O(n^2)\)，就过了。可以放一下代码：

code

#include<bits/stdc++.h>
// #include<windows.h>
using namespace std;

using Yc = long long;
const Yc zyc = 3010 ;

Yc n,X,inf;
struct Zyc{

    Yc pos,f,i;

    friend bool operator <(Zyc a,Zyc b){
        return a.pos<b.pos;
    }

};
vector<Zyc>a;
Yc flag[zyc];
Yc f[zyc][zyc][2];

inline Yc read(){

    Yc x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;

}

inline Yc Dfs(Yc l,Yc r,Yc now){

    if(f[l][r][now]!=0x3f3f3f3f3f3f3f3f)  return f[l][r][now];
    Yc minv=inf,pos=(now==0)?a[l].pos:a[r].pos;

    if(r+1<n){
        if(a[r+1].f==1) //终点
            minv=min(minv,a[r+1].pos-pos);
        else  if(a[r+1].f==2&&flag[a[r+1].i])//墙且有锤子
            minv=min(minv,a[r+1].pos-pos+Dfs(l,r+1,1));
        else  if(a[r+1].f==3){//锤子
            flag[a[r+1].i]=1;
            minv=min(minv,a[r+1].pos-pos+Dfs(l,r+1,1));
            flag[a[r+1].i]=0;
        }
    }
    if(l>0){
        if(a[l-1].f==1)//终点
            minv=min(minv,pos-a[l-1].pos);
        else  if(a[l-1].f==2&&flag[a[l-1].i])
            minv=min(minv,pos-a[l-1].pos+Dfs(l-1,r,0));
        else  if(a[l-1].f==3){
            flag[a[l-1].i]=1;
            minv=min(minv,pos-a[l-1].pos+Dfs(l-1,r,0));
            flag[a[l-1].i]=0;
        }
    }

    f[l][r][now]=minv;
    return minv;

}

signed main(){

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

    memset(f,0x3f,sizeof(f));
    n=read();X=read();inf=LONG_LONG_MAX;

    a.push_back({0,0,0});a.push_back({X,1,0});

    for(Yc i=1;i<=n;i++)
        a.push_back((Zyc){read(),2,i});
    for(Yc i=1;i<=n;i++)
        a.push_back((Zyc){read(),3,i});
    
    sort(a.begin(),a.end());

    n=2*n+2;
    for(Yc i=0;i<n;i++)
        if(a[i].f==0){
            Yc t=Dfs(i,i,0);
            if(t==inf||t<0)  cout<<-1;
            else  cout<<t;
            cout<<'\n';
        }

    // system("pause");

    return 0;

}

代码简洁，思路清晰，通俗易懂，我一遍就码对了，甚至都没有debug。