menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】OI日记 · 8月6号——刷题Day!
2020-08-06 | 【OI】 | 暂无评论 | 430 次阅读 | 403字

    有句话说得好:“刷题一时爽,一直刷题一直爽”。今天真的就结结实实刷了一天的题,刷得脑阔都晕了。那好,我就先放上做题记录:

    今天,我们来讲两道蓝题吧。

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;
}

调试信息请自动忽略
    好,今天就到这里,明天休息一天,后天见!

None
发表评论
暂无评论
textsms
account_circle
email
link