ARC068F Solitaire

2024-01-13 22:10
文章标签 solitaire arc068f

本文主要是介绍ARC068F Solitaire,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

Problem Statement

Snuke has decided to play with N cards and a deque (that is, a double-ended queue). Each card shows an integer from 1 through N, and the deque is initially empty.

Snuke will insert the cards at the beginning or the end of the deque one at a time, in order from 1 to N. Then, he will perform the following action N times: take out the card from the beginning or the end of the deque and eat it.

Afterwards, we will construct an integer sequence by arranging the integers written on the eaten cards, in the order they are eaten. Among the sequences that can be obtained in this way, find the number of the sequences such that the K-th element is 1 . Print the answer modulo 109+7.

Constraints

  • 1≦K≦N≦2,000

Input

The input is given from Standard Input in the following format:
NK

Output

Print the answer modulo 109+7.

Sample Input 1

2 1

Sample Output 1

1

There is one sequence satisfying the condition: 1,2 . One possible way to obtain this sequence is the following:

  • Insert both cards, 1 and 2 , at the end of the deque.
  • Eat the card at the beginning of the deque twice.

思路:

将第一步插入后的序列(插入序列)想象成两个单调递减栈A和B,其中一个栈最小值为1,不妨设这个栈为A.(两个栈按图中线连起来即得到插入序列)

图1

 依次从两个栈中取出元素,得到删除序列.取元素的步骤如图1所示

①从A取出1上全部元素及B中部分元素(可能没有也可能是B中全部元素)

②取出A中的1

③取出B中剩余元素,B中剩余n-k个元素,共2^{n-k-1}种取法.(最后一种元素无论从序列左边取还是右边取都会加到删除序列的最后一个)

问题即为第一步的取法有多少种.

基本思想:动态规划

图2

dp[i][j]表示添加了i个元素,其中最小值为j的删除队列的个数.

i为栈A顶部取出的部分元素及栈B顶部取出的部分元素,顺序不唯一.

j可能是A取出元素的最小值或B取出的元素的最小值,即从栈中取出的最下面一个元素.

可以表示成如图2所示,即从stack1顶部取走部分元素,最后一个为j,从stack2顶部取走部分元素.

考虑这种情况的上一步.

如果上一步是把stack1中的j加入删除队列,即取出j,那么状态转移方程可表示为

dp[i][j]=dp[i-1][j+1]+dp[i-1][j+2]...+dp[i-1][n]=\sum_{m=j+1}^n dp[i-1][m]

如果上一步是将stack2中的元素加入删除队列,由于当前j为最小值,所以上一步最小值也必定为j,即

dp[i][j]=dp[i-1][j]

需要注意此处stack2必须不为空,即j<=n-i+1.

综合来看得到状态转移方程:

dp[i][j]=\sum_{m=j}^n dp[i-1][m]

初始状态:

dp[1][j]=1 \quad j=1,2,3...n

代码:

import java.util.Scanner;class Main {static int mod = 1000000007;public static void main(String[] args) {int ans = 0;Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();int[][] dp = new int[n+1][n+1];//初始化状态for(int j = 1;j<=n;j++) {dp[1][j]=1;}//dpfor(int i = 2;i<=k;i++) {int sum = dp[i-1][n];for(int j = n-1;j>=1;j--) {sum=(sum+dp[i-1][j])%mod;if(j<=n-i+1) {dp[i][j]=sum;}}}//乘后n-k个元素的组合ans = (dp[k][1]-dp[k-1][1]+mod)%mod;for(int i = 1;i<=n-k-1;i++) {ans = (ans<<1)%mod;}System.out.println(ans);in.close();}
}

参考:

[1]【ARC068F】Solitaire 【动态规划】_ez_2016gdgzoi471的博客-CSDN博客_arc068f

这篇关于ARC068F Solitaire的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/602960

相关文章

【UVA】10651-Pebble Solitaire(直接递归或者记忆化)

不知道这个题UVA的数据是怎么的,用2个方法交了,第一次直接递归,第二次记忆化剪枝,时间竟然一样!? 直接郁闷了,简单的二进制表示状态和二进制运算。 14145176 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:18:21 #include<cstdio>#include<algorithm>#inclu

uva 10651 Pebble Solitaire(动态规划:记忆化搜索)

题意是对于当前的一行,求出转换到不能再转换状态所需的最多步数 题目看起来没有思路,感觉找不到状态转移方程 看了别人的题解才知道这个题还是很容易的 但是需要想到stl map 我们用dp[s]表示把s转换为不能转换所需的最多步数 如果可以由s转换到t 则有:dp[s] = max(dp[s], dp[t]) 因为起始状态不好找,所以用记忆化搜索来写比较好 代码如下: #incl

HDU 1401 Solitaire(双向搜索)

题目:LINK 题意: 在一个8×8的棋盘中,给定你4个棋子A,再给你4个棋子B,问你在8步之内能不能够从A位置移动到B位置; 规则:棋子能能上下左右移动,同时能跳过相邻的棋子到达相邻棋子的空地方; 如果直接搜索无论是bfs还是dfs都会TLE的,可以发现无论是从开始的棋盘搜索到最终的棋盘,还是从最终的棋盘搜索到开始的棋盘是一样的。 所以我们从开始的棋盘搜索4步,从最终的棋盘搜索4步,检测

ZJU1505 Solitaire - 双向广搜解决空间问题

2007-07-26 03:40:42 Accepted 1505 C++ 00:00.63 1648K Tiaotiao 现在是凌晨3点45分.这次的胜利实在是来之不易,在我即将崩溃之时,眼前突然一片光明~AC! 真是所谓柳暗花明峰回路转喜从天降心旷神怡雪中送炭啊...:) 下面转入正题,这次解决的题目是在时间和空间都相当困难的情况下,使用了传说中相当繁琐的双向搜索,高中的时候用笔写过

UVa 10651 Pebble Solitaire (DPbitset)

10651 - Pebble Solitaire Time limit: 3.000 seconds  http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1592 化为二进制进行状态转移,详见代码。 完整代码:

LOJ #2731 [JOI2016春季合宿]Solitaire (DP、组合计数)

题目链接 https://loj.ac/problem/2731 题解 首先一个很自然的思路是,设\(dp[i][j]\)表示选了前\(i\)列,第\(2\)行第\(i\)列的格子是第\(j\)个被填上的。 还要加个第三维\(0/1\),表示第\(2\)行第\(i\)列不是/是这一列最后一个被填上的(这决定了它是被上下填上还是被左右填上)。 转移: 若第\(2\)行第\(i\)列是棋子,则所有的

面向对象课设实验——solitaire(java实现)

一、读懂题目! 一开始看题目我就看了很久,面对下面这张图解我完全看不懂,不知道这个游戏到底怎么进行,后来在win10自带的游戏里找到了这个游戏才知道是要做什么。(做一个项目之前必须得完完全全理解这个项目具体的要求是什么,不能摸棱两可) (点击solitaire进去后选择经典单人游戏即可感受游戏) 游戏说明:将一副扑克牌去掉大小王,只剩下四个花色的1-13,将这些牌放进四种卡堆中,1、dec

英语题目翻译——OJ_ 200:Solitaire

题目:200:Solitaire(OpenJudge - 200:Solitaire) 翻译: 单人纸牌游戏是一种在8x8的棋盘上玩的游戏。棋盘的行和列分别从上到下和从左到右编号为1到8。 黑板上有四个完全相同的部分。在每一次移动中它可以: 将一块移动到相邻的空字段(上、下、左、右), 跳过相邻的一块到一个空的领域(上,下,左、右)。 在上面所示的配置中,每个部件允许移动4次。例如:第

A - Casimir‘s String Solitaire

题意:         t个测试样例,每行有一个字符串,由A,B,C,三个字母组成。         有两个操作:                 他可以从字符串的任意位置上精确地擦除一个字母“A”和一个字母“B”(这些字母不必相邻)                 他可以从字符串任意位置上精确地删除一个字母“B”和一个字母“C”(这些字母不必相邻)。         问是否可以变成空串

CodeForces 1266 E Spaceship Solitaire

题意: 主人公想要造宇宙飞船,所以需要N种物资,每种物资的需求量是 a i a_{i} ai​个。然后呢,如果我们没有任何加速器的话,总的时间需求是 ∑ i n a i \sum_{i}^{n}{a_{i}} ∑in​ai​,但是现在我们有“里程碑”加速器! 里程碑加速器是这样的 「 S , T , U 」 「S,T,U」 「S,T,U」 我们如果有 T T T个 S S S物资的话,我们可