dp

我不是女神ヾ 2022-04-10 09:52 152阅读 0赞

题目链接：[http://acm.upc.edu.cn/problem.php?cid=1028&pid=3][http_acm.upc.edu.cn_problem.php_cid_1028_pid_3]

刚刚做的比赛的一道dp题，感觉不错，就拿出来分享一下：

思路：

//dp\[i\]\[j\]\[k\]表示前i个字符算出的值是j并且最后一位为k(0/1)的数的个数  
//dp\[i\]\[j\]\[0\]=dp\[i-1\]\[j\]\[0\]+dp\[i-1\]\[j\]\[1\];  
//dp\[i\]\[j\]\[1\]=dp\[i-1\]\[j-1\]\[1\]+dp\[i-1\]\[j\]\[0\];

下面的就简单了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<algorithm>
     5 using namespace std;
     6 int dp[110][110][2];
     7 //dp[i][j][k]表示前i个字符算出的值是j并且最后一位为k(0/1)的数的个数
     8 //dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
     9 //dp[i][j][1]=dp[i-1][j-1][1]+dp[i-1][j][0];
    10 
    11 
    12 int main(){
    13     int _case,t,n,k;
    14     dp[1][0][0]=dp[1][0][1]=1;
    15     for(int i=2;i<=100;i++){
    16         for(int j=0;j<i;j++){
    17             dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
    18             if(j>0){
    19                 dp[i][j][1]=dp[i-1][j-1][1]+dp[i-1][j][0];
    20             }else
    21                 dp[i][j][1]=dp[i-1][j][0];
    22         }
    23     }
    24     scanf("%d",&_case);
    25     while(_case--){
    26         scanf("%d%d%d",&t,&n,&k);
    27         printf("%d %d\n",t,dp[n][k][0]+dp[n][k][1]);
    28     }
    29     return 0;
    30 }
    31 
    32 
    33

[http_acm.upc.edu.cn_problem.php_cid_1028_pid_3]: http://acm.upc.edu.cn/problem.php?cid=1028&pid=3
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220401/7bda894cce0f4d80bbb6d3031ff47e6a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 dp学习

给定一个m行n列的矩阵，矩阵每个元素是一个正整数，你现在在左上角（第一行第一列），你需要走到右下角（第m行，第n列），每次只能朝右或者下走到相邻的位置，不能走出矩阵。走过的数的

爱被打了一巴掌/ 2022年08月21日 00:11/ 0 赞/ 94 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 284 阅读

相关 dp

题目链接：[http://acm.upc.edu.cn/problem.php?cid=1028&pid=3][http_acm.upc.edu.cn_problem.php_

我不是女神ヾ/ 2022年04月10日 09:52/ 0 赞/ 153 阅读

相关滑雪DP

题目描述 Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Mic

待我称王封你为后i/ 2022年03月19日 09:10/ 0 赞/ 173 阅读

相关 dp协议

udp(发消息) - 在线播放视频\\qq发消息\\微信消息不需要建立连接就可以通信的不占用连接\\不可靠(消息因为网络不稳定丢失)\\速度快 udp

太过爱你忘了你带给我的痛/ 2021年12月17日 09:05/ 0 赞/ 186 阅读

相关 DP专辑

　　今天练了一波DP。时间紧迫我就只贴代码了。 20141120 fzu2129 [http://acm.fzu.edu.cn/problem.php?pid=2129]

秒速五厘米/ 2021年12月14日 10:51/ 0 赞/ 221 阅读

相关区间dp

让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小

小鱼儿/ 2021年11月26日 19:50/ 0 赞/ 383 阅读

相关【BZOJ 2121】（字符串DP，区间DP）

> 2121: 字符串游戏 > > Description > > BX正在进行一个字符串游戏，他手上有一个字符串L，以及其他一些字符串的集合S，然后他可以进行以下

今天药忘吃喽~/ 2021年10月01日 00:08/ 0 赞/ 383 阅读

相关 DP(背包)

自用向 DP 背包 01背包 normal f i = m a x ( f i , f i − v + w ) f\_i = max(f

﹏ヽ暗。殇╰゛Y/ 2021年09月07日 06:08/ 0 赞/ 420 阅读

相关 dp心得

DP心得动态规划是把一个问题分成若干个子问题，其中每一步求取最优的解，然后把这些解保存下来，再利用这些已有的解推出之后所要求的。应该满足如下条件： 1.最优子结构

约定不等于承诺〃/ 2021年07月16日 12:21/ 0 赞/ 389 阅读