本文最后更新于 2024年9月7日 下午
SP703 Mobile Service
Problem Link
Solutioon
设 fi,x,y,z 表示处理到第 i 个请求,三个人分别在 x,y,z 位置上时的最小值。注意到三个人中一定会有一个人在上一个请求的位置,故状态可以优化为 fi,x,y,此时令 z=qi−1 则有
fi+1,x,y=min(fi+1,x,y,fi,x,y+cz,qi+1)fi+1,x,z=min(fi+1,x,z,fi,x,y+cy,qi+1)fi+1,y,z=min(fi+1,y,z,fi,x,y+cx,qi+1)
初值 q0=1,f0,2,3=0。
Core Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| 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
设 fi 表示到 si 时最长括号匹配,从头开始线性扫描,扫到后半括号时判断是否能组成匹配。
显然,当且仅当在其 前面括号匹配长度(fi−1)的前一个字符是同类型的前半括号(即类似
(xxx)
)。
由此可得式子 fi=fi−1+fi−fi−1−2+2。其中 i−fi−1−2 表示前半括号。
Core Code
1 2 3 4 5 6 7 8 9 10 11
| 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;
|