杂题乱记

SP703 Mobile Service

Problem Link

Solutioon

设 $f_{i,x,y,z}$ 表示处理到第 $i$ 个请求，三个人分别在 $x,y,z$ 位置上时的最小值。注意到三个人中一定会有一个人在上一个请求的位置，故状态可以优化为 $f_{i,x,y}$，此时令 $z=q_{i-1}$ 则有

$$f_{i+1,x,y}=\min(f_{i+1,x,y},f_{i,x,y}+c_{z,q_{i+1}})\\ f_{i+1,x,z}=\min(f_{i+1,x,z},f_{i,x,y}+c_{y,q_{i+1}})\\ f_{i+1,y,z}=\min(f_{i+1,y,z},f_{i,x,y}+c_{x,q_{i+1}})$$

初值 $q_0=1, f_{0,2,3}=0$。

Core Code

for(int i=0;i<n;i++) {
    for(int x=1;x<=l;x++) {
        for(int y=1;y<=l;y++) {
            int z=q[i];
            if(x==y || x==z || y==z) continue;
            f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[z][q[i+1]]);
            f[i+1][z][y]=min(f[i+1][z][y],f[i][x][y]+c[x][q[i+1]]);
            f[i+1][x][z]=min(f[i+1][x][z],f[i][x][y]+c[y][q[i+1]]);
        }
    }
}
int ans=INF;
for(int x=1;x<=l;x++) {
    for(int y=1;y<=l;y++) {
        int z=q[n];
        if(x==y || x==z || y==z) continue;
        ans=min(ans,f[n][x][y]);
    }
}

P4310 绝世好题

待填坑

P1944 最长括号匹配

Problem Link

Solution

设 $f_i$ 表示到 $s_i$ 时最长括号匹配，从头开始线性扫描，扫到后半括号时判断是否能组成匹配。

显然，当且仅当在其 前面括号匹配长度（$f_{i-1}$）的前一个字符是同类型的前半括号（即类似
(xxx)）。

由此可得式子 $f_i=f_{i-1}+f_{i-f_{i-1}-2}+2$。其中 $i-f_{i-1}-2$ 表示前半括号。

Core Code

for(int i=1;i<=n;i++) {
    if((s[i]==')' && s[i-f[i-1]-1]=='(') || (s[i]==']' && s[i-f[i-1]-1]=='[')) f[i]=f[i-1]+f[i-f[i-1]-2]+2;
    if(ans<f[i]) {
        ans=f[i];
        last=i;
    }
}
for(int i=last-ans+1;i<=last;i++) {
    putchar(s[i]);
}
el;