做网站如何购买服务器,自己做的网站注册用户无法收到激活邮箱的邮件,做网站湖州,沈阳做网站 熊掌号正题
题目链接:https://loj.ac/problem/2687 题目大意
三个操作: hhh光标向前移动一格xxx删除光标处字母fcf\ cf c移动到下一个字符ccc(算两次操作)
然后fff操作不能对字符eee使用#xff0c;然后求最少操作次数删除所有的eee。 解题思路
线头dpdpdp。 设fi,jf_{i,j}fi,j…正题
题目链接:https://loj.ac/problem/2687 题目大意
三个操作:
hhh光标向前移动一格xxx删除光标处字母fcf\ cf c移动到下一个字符ccc(算两次操作)
然后fff操作不能对字符eee使用然后求最少操作次数删除所有的eee。 解题思路
线头dpdpdp。 设fi,jf_{i,j}fi,j表示越过iii一次然后fff操作是到jjj字符的最小操作次数。 gi,j,kg_{i,j,k}gi,j,k表示越过iii三次然后在到iii之前的fff操作到jjj字符在iii之后的fff操作到kkk字符的最小操作次数。
然后动态转移: fi,j{fi−1,j(j!si,!needi)fi−1,si2gi−1,si,j(j!si)gi−1,si,si2f_{i,j}\left\{\begin{matrix} f_{i-1,j}(j!s_i,!need_i) \\ f_{i-1,s_i}2 \\ g_{i-1,s_i,j}(j!s_i) \\ g_{i-1,s_i,s_i}2 \\\end{matrix}\right.fi,j⎩⎪⎪⎨⎪⎪⎧fi−1,j(j!si,!needi)fi−1,si2gi−1,si,j(j!si)gi−1,si,si2 gi,j,k{fi−1,j3(j!si)fi−1,si5gi−1,j,k1(j,k!si)gi−1,j,si3(j!si)gi−1,si,k3(k!si)gi−1,si,si5g_{i,j,k}\left\{\begin{matrix} f_{i-1,j}3(j!s_i) \\ f_{i-1,s_i}5 \\ g_{i-1,j,k}1(j,k!s_i) \\ g_{i-1,j,s_i}3(j!s_i) \\ g_{i-1,s_i,k}3(k!s_i) \\ g_{i-1,s_i,s_i}5 \end{matrix}\right.gi,j,k⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧fi−1,j3(j!si)fi−1,si5gi−1,j,k1(j,k!si)gi−1,j,si3(j!si)gi−1,si,k3(k!si)gi−1,si,si5
详细的的看这篇dalaoの题解\texttt{dalaoの题解}dalaoの题解lt;−pleasechecktherelt;-please\ check\ there−please check there codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N70100;
int n,m,ans,s[N],must[N],f[N][11],need1,g[N][11][11];
void get_min(int x,int y)
{if(yx) xy;}
int main()
{scanf(%d\n,n);for(int i1;in;i){char c;scanf(%c,c);if(ce)ans(need1)*2;else{s[m]c-a;must[m]need;need0;}}memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));f[0][s[1]]0;for(int i1;im;i){for(int j0;j11;j){if(!must[i]j!s[i])get_min(f[i][j],f[i-1][j]);get_min(f[i][j],f[i-1][s[i]]2);if(j!s[i])get_min(f[i][j],g[i-1][s[i]][j]);get_min(f[i][j],g[i-1][s[i]][s[i]]2);for(int k0;k11;k){if(j!s[i])get_min(g[i][j][k],f[i-1][j]3);get_min(g[i][j][k],f[i-1][s[i]]5);if(j!s[i]k!s[i])get_min(g[i][j][k],g[i-1][j][k]1);if(j!s[i])get_min(g[i][j][k],g[i-1][j][s[i]]3);if(k!s[i])get_min(g[i][j][k],g[i-1][s[i]][k]3);get_min(g[i][j][k],g[i-1][s[i]][s[i]]5);}}}printf(%d,f[m][10]ans-2);
}
