1260. Nudnik Photographer dp

发布时间:2014-10-22 14:32:31编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"1260. Nudnik Photographer dp",主要涉及到1260. Nudnik Photographer dp方面的内容,对于1260. Nudnik Photographer dp感兴趣的同学可以参考一下。

题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1260 描述:1,2,3,,,n.排成一排,第一个数必须是1,且相邻的两个数差的绝对值 <= 2. 思路:一开始没想出来递推式,(动态规划没怎么做过,碰到都是泪啊,该多练习了)。就用dfs写了一个程序求前面几十个(大概n=30左右时间就不能忍受了) #include <iostream> #include <cstdio> #include <cstring> int a[60], ans, vis[60], n; void dfs(int pos) { if (pos == n) { ++ans; return; } else { for (int i = 2; i <= n; ++i) if (!vis[i] && abs(i - a[pos-1]) <= 2) { vis[i] = 1; a[pos] = i; dfs(pos+1); vis[i] = 0; } } } int main() { while (scanf("%d", &n) != EOF) { memset(vis, 0, sizeof(vis)); ans = 0; for (int i = 0; i < n; ++i) a[i] = i + 1; dfs(1); printf("%d\n", ans); } system("pause"); return 0; } 求出来前面一些答案: n  =   1 2 3 4 5 6 7   8    9    10   11  12   13 ans=   1 2 2 4 6 9 14  21   31   46   68  100  147 然后就发现了规律f[n] = f[n-1] + f[n-2] - f[n-5],后来看Discussion有人的数学公式是f[i] = f[i-1] + f[i-3] + 1,其实是一样的,递推一下就行了。 证明: f[i] = f[i-1] + f[i-3] + 1 所以 f[i-2] = f[i-3] + f[i-5] + 1 所以: f[i-2] - f[i-3] - f[i-5] = 1 带入f[i]得: f[i] = f[i-1] + f[i-3] + f[i-2] - f[i-3] - f[i-5]  = f[i-1] + f[i-2] - f[i-5]。 先列个表: n=1 1 n=2 1 2 n=3 1 2 3 ........ 1 3 2 n=4 1 2 3 4 1 2 4 3 ........... 1 3 2 4 ............ 1 3 4 2 n=5 1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 1 2 4 5 3 .............. 1 3 2 4 5 .............. 1 3 5 4 2 f[n]的构造方式有三种:(注意以上几组数据对于相同的n,虚线分割的数据是不同的构造方式) (1) 2 放在 2nd 位置,有f[n-1]种 (2) 3 放在 2nd 位置, 2在 3rd 位置,此时 4 必须在 4th 位置。有f[n-3]种 (3) 最有还有 1 种按照1 3 5 .... 8 6 4 2 即奇增偶减的方式。 f[n] = f[n-1] + f[n-3] + 1


上一篇:SQLserver2008全文检索使用方法
下一篇:微信开放平台开发(微信开放平台:朋友圈API参考文档)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款