首页 > 其他分享 >P4170 [CQOI2007]涂色(思维好题)

P4170 [CQOI2007]涂色(思维好题)

时间:2023-03-05 19:33:07浏览次数:66  
标签:ch const int 好题 P4170 涂色 dp define

P4170 [CQOI2007]涂色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

设DP[i][j]为完成(i-j)区间的最少涂鸦次数。

考虑dp[i][j]的转移:
重点:如果s[i]==s[j],dp[i][j]=min(dp[i][j-1],dp[i+1][j]),因为颜色一样,只需要首次涂色的时候多图一个。

那为什么不是dp[i][j]=dp[i-1][j+1]+1呢?举例:RRWRR dp[1][5]!=dp[2][4]+1。

其他正常区间dp转移即可.

初始化:dp[i][i]=1.

 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=110;
//const int M=;
const int inf=0x3f3f3f3f;     
//const ll INF=0x3ffffffffffff;
int T,n,dp[N][N];
char s[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) dp[i][j]=inf;
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(s[i]==s[j]) dp[i][j]=min(dp[i][j-1],dp[i+1][j]);
            for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
    printf("%d",dp[1][n]);
    return 0;
}

 

 

标签:ch,const,int,好题,P4170,涂色,dp,define
From: https://www.cnblogs.com/Willette/p/17181396.html

相关文章

  • 超级书架2 计蒜客 - T1736(01背包应用,好题)
    题意:FarmerJohn最近为奶牛们的图书馆添置了一个巨大的书架,尽管它是如此的大,但它还是几乎瞬间就被各种各样的书塞满了。现在,只有书架的顶上还留有一点空间。所有N(1≤N≤......
  • Codeforces Round #521 (Div. 3) D. Cutting Out 好题字符串
    D.CuttingOuttimelimitpertest3secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputYouaregivenanarray ss consistingof n......
  • Codeforces Round #520 (Div. 2) A. A Prank 好题
    A.APranktimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputJATCandhisfriendGiraffearecurrentlyinthei......
  • UVA12096 The SetStack Computer 栈的应用 好题
    题意翻译对于一个以集合为元素的栈,初始时栈为空。输入的命令有如下几种:PUSH:将空集{}压栈DUP:将栈顶元素复制一份压入栈中UNION:先进行两次弹栈,将获得的集合A和B取并集,将结......
  • Codeforces1059C. Sequence Transformation 好题 没做出来 数学思维
     C.SequenceTransformationtimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputLet'scallthefollowingproce......
  • 51NOD 1278 相离的圆(二分 + 排序 好题)
    平面上有N个圆,他们的圆心都在X轴上,给出所有圆的圆心和半径,求有多少对圆是相离的。例如:4个圆分别位于1,2,3,4的位置,半径分别为1,1,2,1,那么{1,2},{1,3}{2,3}{2,4......
  • 51nod 1138 连续整数的和 好题
    给出一个正整数N,将N写为若干个连续数字和的形式(长度>=2)。例如N=15,可以写为1+2+3+4+5,也可以写为4+5+6,或7+8。如果不能写为若干个连续整数的和,则输出NoS......
  • 超级无敌神仙炫酷无敌原神大王好题。
    都是神题,难度3000上下。有些都是看题解做的,就当涨知识见世面了。学OI没做这些题,简直就是打游戏不玩原神,看vtb不看東雪蓮,听歌不听曹万江,成功学不学cjx,看闲话不看韩神,只......
  • 差分约束好题
    1、MagicProblem-7176(hdu.edu.cn)思路:求的是区间总和,所以考虑和前缀和进行结合,将前缀和a[i](前i个数的前缀和)作为边权。然后考虑限制条件。首先,区间[l,r]的总和小于......
  • P2657 [SCOI2009] windy 数 数位DP好题
    P2657[SCOI2009]windy数-洛谷|计算机科学教育新生态(luogu.com.cn)数位DP好题主要问题是:不含前导零且相邻两个数字之差至少为 2solution:现在枚举到了第i位......