首页 > 其他分享 >P1057 [NOIP2008 普及组] 传球游戏

P1057 [NOIP2008 普及组] 传球游戏

时间:2024-05-20 16:54:23浏览次数:29  
标签:传球 nxt int bef NOIP2008 P1057 include dp

链接:https://www.luogu.com.cn/problem/P1057
思路:左手倒右手,建立递推方程
建立初始参数:定义dp[j][k]是第k次,以j结尾的方法,就是传k次最后传到j的方法。
那么状态转移方程:dp[j][k]=dp[next][k-1]+dp[before][k-1]
其中before是j的前一个元素(j-1);next是j的后一个元素j+1。同时要注意从1到n的转换
nxt = (!nxt) ? n : nxt, bef = (bef) ? bef : n;
没想到一次过了OWO!!

#define _CRT_SECURE_NO_WARNINGS 0
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;
const int N = 50;
ll dp[N][N];
int main()
{
	int n, m; cin >> n >> m;
	memset(dp, 0, sizeof(dp));
	dp[1][0] = 1;
	for (int k = 1; k <= m; k++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (j - 1 <= k or 1 + n - j <= k)
			{
				int nxt = (j + 1) % n, bef = (j - 1) % n;
				nxt = (!nxt) ? n : nxt, bef = (bef) ? bef : n;
				dp[j][k] += dp[nxt][k - 1] + dp[bef][k - 1];
			}
		}
	}
	cout << dp[1][m];

	return 0;
}

标签:传球,nxt,int,bef,NOIP2008,P1057,include,dp
From: https://www.cnblogs.com/zzzsacmblog/p/18202319

相关文章

  • P1155 [NOIP2008 提高组] 双栈排序
    P1155[NOIP2008提高组]双栈排序有思维的二分图染色题。对于“双”类的题目,我们通常分开考虑单个时的性质。对于一个栈,有一个基本的定理:若出现\(i<j<k\),有\(a_k<a_i<a_j\),那么一定不合法,即没有合法的出栈顺序使之有序。对于两个栈,我们相当于把序列分成两部分,使每部分之间......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    P1149[NOIP2008提高组]火柴棒等式题目给你\(n\)根火柴棍,你可以拼出多少个形如\(A+B=C\)的等式?等式中的\(A\)、\(B\)、\(C\)是用火柴棍拼出的整数(若该数非零,则最高位不能是\(0\))。用火柴棍拼数字\(0\sim9\)的拼法如图所示:注意:加号与等号各自需要两根火柴棍;如果......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    目描述给你 n 根火柴棍,你可以拼出多少个形如A+B=C 的等式?等式中的 A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 00)。用火柴棍拼数字 0∼90∼9 的拼法如图所示:注意:加号与等号各自需要两根火柴棍;如果A=B,则+B=C 与B+A=C 视为不同的等式(≥0A,B,C≥......
  • 洛谷 P1006 [NOIP2008 提高组] 传纸条
    题意:传纸条,跟方格取数一样,但是两条路径不能有重复的。思路:还是一样的走,但是x1跟x2不能相等,包括现在跟上一个状态。总结:看了题解,发现题解大多数都是逻辑不正确的,更有离谱的是数组范围都不加特判,数组访问越界但是可以ac的情况,数据太烂了,放个自以为正确的思路吧,发现之前自己提交的......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    题目链接:本题比较重要的点在于判断加数的范围,即枚举的范围大小。由于题目已知\(n\leqslant24\),且用数字\(1\)拼成的数尽可能大。由于\(1111+1=1112\)已经用了\(25\)根小棒,已经超过了题目\(24\)根小棒的数据范围,所以上界为\(1111\)。#include<cstdio>inta[10]=......
  • 【洛谷】 P1006 [NOIP2008提高组]传纸条
    题目描述小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排坐成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,......
  • C++ [NOIP2008 普及组] ISBN 号码
    文章目录一、题目描述[NOIP2008普及组]ISBN号码题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2提示二、参考代码一、题目描述[NOIP2008普及组]ISBN号码题目描述每一本正式出版的图书都有一个ISBN号码与之对应,IS......
  • P1055 [NOIP2008 普及组] ISBN 号码
    P1055[NOIP2008普及组]ISBN号码[NOIP2008普及组]ISBN号码题目描述每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括\(9\)位数字、\(1\)位识别码和\(3\)位分隔符,其规定格式如x-xxx-xxxxx-x,其中符号-就是分隔符(键盘上的减号),最后一位是识别码,例如0-6......
  • P1149 [NOIP2008 提高组] 火柴棒等式
    [NOIP2008提高组]火柴棒等式题目描述给你\(n\)根火柴棍,你可以拼出多少个形如\(A+B=C\)的等式?等式中的\(A\)、\(B\)、\(C\)是用火柴棍拼出的整数(若该数非零,则最高位不能是\(0\))。用火柴棍拼数字\(0\sim9\)的拼法如图所示:注意:加号与等号各自需要两根火柴棍;如果\(......
  • [NOIP2008 提高组] 笨小猴
    [NOIP2008提高组]笨小猴来自洛谷:[https://www.luogu.com.cn/problem/P1125]Openjudge:[http://noi.openjudge.cn/ch0109/06/]普及难度,其实不难。我们先审题.设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数第一行输入字符串,......