有句话说得好:“刷题一时爽,一直刷题一直爽”。今天真的就结结实实刷了一天的题,刷得脑阔都晕了。那好,我就先放上做题记录:
今天,我们来讲两道蓝题吧。
P3205 [HNOI2010]合唱队
这道题的转移方程比较简单,我们设$f[i][j][k]$表示上一次将人添加到左或右从而形成的i-j的字串的方案总数。其中i,j表示范围,k=0表示上一次添加在左边,k=1表示上一次添加到右边。这样,转移方程就出来了:
$f[i][j][1]+=f[i+1][j][0] \quad (s[l]<s[l+1])$
$f[i][j][0]+=f[i+1][j][1] \quad (s[l]<s[r])$
$f[i][j][1]+=f[i][j-1][0] \quad (s[r]>s[l])$
$f[i][j][1]+=f[i+1][j][1] \quad (s[r]>s[r-1])$
这里的s数组表示理想队形。不过这里要注意,一定要先把小范围给求了,再去求大范围。其它注意事项见代码(CPP):
#include <bits/stdc++.h>
#define MOD 19650827
#define MAXN 1005
using namespace std;
int n;
int s[MAXN];
int f[MAXN][MAXN][2];
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>s[i];
for (int i=1;i<=n;i++)
f[i][i][0]=1;
for (int i=1;i<n;i++)
{
for (int l=1;l<=n-1;l++)
{
int r=l+i;
if (s[l]<s[l+1]) f[l][r][0]=(f[l][r][0]+f[l+1][r][0])%MOD;
if (s[l]<s[r]) f[l][r][0]=(f[l][r][0]+f[l+1][r][1])%MOD;
if (s[r]>s[l]) f[l][r][1]=(f[l][r][1]+f[l][r-1][0])%MOD;
if (s[r]>s[r-1]) f[l][r][1]=(f[l][r][1]+f[l][r-1][1])%MOD;
}
}
cout<<(f[1][n][0]+f[1][n][1])%MOD<<endl;
return 0;
}
好,第一题做完了,康康第二题:
P4170 [CQOI2007]涂色
这道题相对之下没这么直观(反正本蒟蒻是这么想的),所以转移方程也相对难想。不过,最终的转移方程还是求出来了。我们设$f[i][j]$为完成i-j涂色需要的最少次数。然后,我们就可以分类讨论了。
若$i==j$时,也就是只涂一个块,当然只需要一次就好,所以$f[i][j]=1$。当$i \neq j$且s[i](目标状态)==s[j]时,我们知道,左右两端点如果颜色相同,那么就只需要在涂最底下一层时多涂一层即可,所以$f[i][j]=min(f[i+1][j],f[i][j-1])$。如果$i \neq j$且$s[i] \neq s[j]$,这时,就来到区间DP了:分成两段。所以综上,完整的转移方程如下:
$$ f[i][j] = \begin{cases} 1 &\quad (i=j) \\ min(f[i+1][j],f[i][j-1]) &\quad (i \neq j,s[i]=s[j]) \\ min(f[l][r],f[l][k]+f[k+1][r]) &\quad (i \neq j,s[i] \neq s[j]) \end{cases} $$
剩下的细节部分,见代码(CPP):
#include <bits/stdc++.h>
#define MAXN 55
using namespace std;
char ch[MAXN];
int f[MAXN][MAXN];
int s[MAXN];
int n;
void input()
{
gets(ch);
n=strlen(ch);
for (int i=0;i<n;i++)
s[i+1]=ch[i]-'A'+1;
}
void let_us_color_it()
{
for (int i=1;i<=n;i++)
f[i][i]=1;
for (int i=1;i<n;i++)
{
for (int j=i+1;j<=n;j++)
f[i][j]=INT_MAX;
}
for (int i=1;i<n;i++)
{
for (int l=1;l<=n-i;l++)
{
int r=l+i;
// cout<<l<<" "<<r<<endl;
if (s[l]==s[r]) f[l][r]=min(f[l+1][r],f[l][r-1]);
else for (int k=l;k<r;k++) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
}
}
}
int main()
{
input();
let_us_color_it();
// for (int i=1;i<=n;i++)
// {
// for (int j=1;j<=n;j++)
// cout<<f[i][j]<<" ";
// cout<<endl;
// }
cout<<f[1][n]-1<<endl;
return 0;
}
调试信息请自动忽略
好,今天就到这里,明天休息一天,后天见!