开发者社区> angel_kitty> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

2017"百度之星"程序设计大赛 - 复赛1003&&HDU 6146 Pokémon GO【数学,递推,dp】

简介: Pokémon GO Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 171    Accepted Submission(s): 104 Problem Description 众所周知,度度熊最近沉迷于 Pokémon GO。
+关注继续查看

Pokémon GO

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 171    Accepted Submission(s): 104


Problem Description
众所周知,度度熊最近沉迷于 Pokémon GO。




今天它决定要抓住所有的精灵球!

为了不让度度熊失望,精灵球已经被事先放置在一个2*N的格子上,每一个格子上都有一个精灵球。度度熊可以选择任意一个格子开始游戏,抓捕格子上的精灵球,然后移动到一个相邻的至少有一个公共点的格子上继续抓捕。例如,(2, 2) 的相邻格子有(1, 1), (2, 1) 和 (1, 2) 等等。

现在度度熊希望知道将所有精灵球都抓到并且步数最少的方案数目。两个方案被认为是不同,当且仅当两个方案至少有一步所在的格子是不同的。
 

 

Input
第一行为T,表示输入数据组数。

每组数据包含一个数N。

●1≤T≤100

●1≤N≤10000
 

 

Output
对每组数据输出方案数目,结果对 1 000 000 007 取模。
 

 

Sample Input
3
1
2
3
Sample Output
2
24
96
Source
分析:

说这道题目是一道dp题目。 不如说这是一道数学题目。

递推公式比较复杂
一共有两个递推数组:
首先设Dn表示从左边或者右边的某个角出发,然后走遍所有格子回到同一列有多少种方法。
明显D1=2,Dn=2*Dn-1
所以Dn=2^n
然后设An表示从某个角出发,走遍所有格子(不一定回到同一列)有多少种方法。
An=Dn+2*An-1+4*An-2
这个递推公式就用统计原理分析出来,分别对应三种不同的走法
Dn对应从这个角走到下一列,然后走遍所有格子回到下一列,再回到这列的走法
2*An-1表示直接走到这列的另一个角,然后再走其他的地方
4*An-2表示走对角线方法走遍前两列,然后走其他的地方
这样答案如果从四个角出发,总数就是4*An
然后分析从某一列开始,假设第i列(1<i<n)
则总数为2*(2*Di-1*An-i+2*Dn-i*Ai-1)
对i从2到n-1全部加和,得到这部分答案
两部分答案加起来,就是总数,经测试无误
比赛是拿java乱搞的,emmmm,别介意啊QAQ
下面给出AC代码:
 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 
 4 public class Main{
 5 
 6     /**
 7      * @param args
 8      */
 9     public static void main(String[] args) {
10         Scanner in=new Scanner(System.in);
11         int mod=1000000007;
12         while(in.hasNextInt())
13         {
14             int T=in.nextInt();
15             for(int a=1;a<=T;a++)
16             {
17                 int n=in.nextInt();
18                 long[] p=new long[10010];
19                 long[] r=new long[10010];
20                 p[1]=1;
21                 for(int i=2;i<=n;i++)
22                 {
23                     p[i]=p[i-1]*2;
24                     p[i]=p[i]%mod;
25                 }
26                 r[1]=1;
27                 r[2]=6;
28                 for(int i=3;i<=n;i++)
29                 {
30                     r[i]=2*r[i-1]+p[i]+4*r[i-2];
31                     r[i]=r[i]%mod;
32                 }
33                 long ans=4*r[n];
34                 for(int i=2;i<=n;i++)
35                 {
36                     ans=ans+((8*p[n-i]*r[i-1])%mod+(8*r[n-i]*p[i-1])%mod)%mod;
37                     ans=ans%mod;
38                 }
39                 System.out.println(n==1?2:ans);
40             }
41         }
42     }
43 
44 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【翻译】在没有安装ASP.NET MVC3的服务器上运行ASP.NET MVC3的程序-scottgu
原文地址: http://weblogs.asp.net/scottgu/archive/2011/01/18/running-an-asp-net-mvc-3-app-on-a-web-server-that-doesn-t-have-asp-net-mvc-3-installed.aspx 为了更符合中文阅读习惯,我对原文做了小幅度修改   最近我们发布了一些新的Web产品 - 包括ASP.NET MVC 3。
1054 0
2017广东工业大学程序设计竞赛初赛 题解&源码(A,水 B,数学 C,二分 D,枚举 E,dp F,思维题 G,字符串处理 H,枚举)
Problem A: An easy problem Description       Peter Manson owned a small house in an obscure street.
780 0
DataWorks百问百答39:VPC网络下adb pg实例引擎如何绑定dataworks工作空间执行任务?
VPC网络下adb pg实例引擎绑定dataworks工作空间任务执行执行指导
0 0
where is list binding done for Opportunity S2 view default 20 returns
Created by Wang, Jerry, last modified on May 20, 2015
0 0
no symbol version section for versioned symbol `memcpy@GLIBC_2.4'
no symbol version section for versioned symbol `memcpy@GLIBC_2.4'
0 0
Google Earth Engine ——MYD11A1 V6产品提供1200×1200公里网格内的每日陆地表面温度(LST)和发射率值数据集
Google Earth Engine ——MYD11A1 V6产品提供1200×1200公里网格内的每日陆地表面温度(LST)和发射率值数据集
0 0
+关注
angel_kitty
我叫Angel_Kitty,当然你也可以叫我笔名,Sakura,喜欢交友,乐于助人,喜欢音乐,热爱ACM竞赛,CTF竞赛,喜欢算法、Web、网络安全、黑科技、机器学习、数学建模,C/C++、C#、Java、Python、HTML5、JavaScript,E都略懂,现在主攻逆向工程
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Go语言路上踩过的坑
立即下载
MySQL 5.7优化不求人
立即下载
泰康保险运维自动化技术实践与前瞻
立即下载