首页 > 代码库 > URAL 1260 A nudnik photographer（DP）
URAL 1260 A nudnik photographer（DP）
A nudnik photographer
大意：
对1到N这些数进行排列，1必须要在最左边，相邻的两个数之间的差值不能超过2，问有多少种排列的方法。
思路：
对座位进行DP，当第一个是1，第二个是2的时候，组合为dp[i-1]；当第一个是1，第二个是3的时候，第三个也确定了是2，组合为dp[i-3]；还有最后一种情况是1357……8642。
所以DP方程为dp[i] = dp[i-1]+dp[i-3]+1。
1 #include <stdio.h> 2 3 int n; 4 int dp[100]; 5 6 int main() 7 { 8 scanf("%d", &n); 9 dp[1] = 1;10 dp[2] = 1;11 dp[3] = 2;12 dp[4] = 4;13 for(int i = 5; i <= 55; ++i){14 dp[i] = dp[i-1]+dp[i-3]+1;15 }16 printf("%d", dp[n]);17 18 return 0;19 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。