GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A40985. $愚蠢的摄影师$

填空题较易

知识点

动态规划递推排列计数

题目描述

愚蠢的摄影师 题目描述 背景 "如果两个人相差一秒出生, 其中一个是小孩, 那么另一个也是小孩. 由此可以推论, 所有人均是小孩." 问题 数计系是一个由N个人组成的大家庭, 分别为1, 2, 3, ..., N岁. 有一次系主任想为全系拍张合照. 需要所有学生站成一排. 起先他想按他们的岁数从小到大安排, 但后来又觉得这样不自然. 于是他建议按如下方案站排: 1岁的在最左边. 每相邻两人不得相差超过2岁. 这样学生的岁数看起来显得很平均(25岁和27岁的人差别很难看出). 存在多种方案满足此要求. 摄影师不想违反系主任的意愿, 就为每种可能的安排分别拍了一张照片. 输入格式 整数N, 1<=N<=55. 输出格式 所拍照片张数. 样例输入 4 样例输出 4

参考答案

#include<stdio.h>
int main()
{
    int N;
    int A[55];
    A[0]=1; //N=1要拍的张数
    A[1]=1; //N=2要拍的张数
    A[2]=2;//N=3要拍的张数
     for(int i=3;i<55;i++)
        A[i]=A[i-1]+A[i-3]+1;
     while(scanf("%d",&N)!=EOF)
        printf("%d\n",A[N-1]);
     return 0;
}

上一题下一题