P1057传球游戏
2024-09-02 16:55:55
这是一道动态规划的水题,难度为提高-。
题意为:n个人围成一个环传球,每一次都可以往左或右传,传m次,问有几种最后传到小明手里的方案数。然后因为一个状态有两个变量,所以我们用dp[][]来存储【传球次数】【当前序号】的方案数,然后我们可以得知每一个最优子结构都是由相邻左边或者右边的两种子结构得来的,所以我们可以得出dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]的方程。再进行特判i==1或i==n即可。
1.分析状态转移方程可以尝试用表格的形式,分析是怎么来的,不拘泥于形式,不一定是max(,)
2.设dp数组时想好状态的完整性
代码
#include<bits/stdc++.h>
#define maxn 35
using namespace std;
int n,m;
int dp[maxn][maxn];//[传球的次数][传到的位置]
int main(){
scanf("%d%d",&n,&m);
dp[][]=;//自己到自己
for(int i=;i<=m;i++){//次数
for(int j=;j<=n;j++){//位置
if(j==){
dp[i][j]=dp[i-][n]+dp[i-][];
}
else if(j==n){
dp[i][j]=dp[i-][n-]+dp[i-][];
}
else{
dp[i][j]=dp[i-][j-]+dp[i-][j+];
}
}
}
cout<<dp[m][];
return ;
}
最新文章
- MAPPING SEGMENTS TO PAGES
- ruby -- 基础学习(五)empty、nil、blank三者之间的区别
- MFC 仿QQ聊天软件(黄花寒)
- apache-maven-3.3.9集成apache-tomcat-7.0.72实现热部署配置细节
- 利用Connect By构造数列
- 基于redis AE异步网络架构
- linq to sql简单使用
- github中origin和upstream的区别(转)
- HTML CSS基础(二)
- Linux命令及架构部署大全
- php curl请求和获取接口数据
- EChart.js 笔记一
- window安装mysql(详细步骤)
- 斜率优化dp的总结
- 修改CKplayer.js 源码解决移动端浏览器全屏不能限制快进的问题
- iOS AppIcon尺寸
- 用python读取stata文件及写入and注意事项
- WCF异常信息
- Spring学习(十八)----- Spring AOP+AspectJ注解实例
- 1、lambda表达式
热门文章
- [LibreOJ 3124]【CTS2019】氪金手游【容斥原理】【概率】【树形DP】
- 【封装工程】OI/ACM常用封装
- 【BZOJ4259】 残缺的字符串
- &#39;vue&#39; 不是内部或外部命令,也不是可运行的程序 或批处理文件
- Jmeter -- 监听 -- 查看每个请求的启动时间等信息
- TCP定时器 之 连接建立定时器
- 【攻克RabbitMQ】常见问题
- Redis的高可用详解:Redis哨兵、复制、集群的设计原理,以及区别
- var $this = $(this)
- RGB-D显著性突出物体(学习)