2132: 中南大学2017年ACM暑期集训前期训练题集(入门题)

水深无声 2022-06-15 06:00 139阅读 0赞

## F: 漫漫上学路 ##

Submit Page  Time Limit: 1 Sec  Memory Limit: 128 Mb  Submitted: 145  Solved: 59

--------------------

## Description ##

对于csuxushu来说，能够在CSU（California State University）上学是他一生的荣幸。CSU校园内的道路设计的十分精巧，由n+1条水平道路和n+1条竖直道路等距交错而成，充分体现了校园深厚的文化底蕴。然而不幸的是CS市每到夏季，天降大雨，使得CSU常常形成“CS海”的奇观，今年，也就是2016年同样也不例外，校园有一半的区域被淹了。  
由于要进行一年一度激动人心的省赛选拔了，起迟了的csuxushu赶紧从寝室背着一包模板前往机房，好奇的csuxushu发现虽然道路被淹了，但是只有左上三角区域受到影响，也就是说他可以在副对角线以下的道路畅通行走。在这个惊人的场景下，csuxushu做了一个惊人的决定，他要算出他有多少种前往机房的最短路线。然而只有10分钟了，这时候他想到了你——全CSU最厉害的程序员来帮助他解决这个问题。  
需要指出的是CSU可以看做左下顶点为csuxushu的寝室（0,0），右上顶点为机房（n,n）的方形区域。

## Input ##

多组数据。每组数据只有一行，为一个整数n（1 ≤n ≤30）。

## Output ##

每组数据输出一行，即由寝室到机房的最短路线方案数。测试数据保证结果为64位整数。

## Sample Input ##

## Sample Output ##

## Hint ##

14条最短路线如下

![x123421_281_29.png.pagespeed.ic.czMDSpFJKr.png][]

题目大意：

这个题目的意思就是给你一个数字N，在N\*N的格子中，以对角线平分，左上角被水淹了，不能行走，问最短路径一共有多少种。

题目解析：

这个题目是一个简单的DP题，我把它转化成了堆木块问题，最后的答案为堆木块的总数+1，经过思考和计算化简可以得到动归方程

a[i]+=a[j]*a[i-j-1];

代码：

#include<iostream>
    using namespace std;
    
    int main()
    {
        int n,i,j;
        long long a[35];
        a[0]=1;
        for(i=1;i<35;i++)
        {
            a[i]=0;
            for(j=0;j<i;j++)
            {
                a[i]+=a[j]*a[i-j-1];
            }
        }
    
        while(cin>>n)
        {
    
            cout<<a[n]<<endl;
        }
        return 0;
    
    }
    
    /**********************************************************************
    	Problem: 1772
    	User: PoorGuy
    	Language: C++
    	Result: AC
    	Time:0 ms
    	Memory:1696 kb
    **********************************************************************/

[x123421_281_29.png.pagespeed.ic.czMDSpFJKr.png]: http://acm.csu.edu.cn/OnlineJudge/upload/201607/x123421,281,29.png.pagespeed.ic.czMDSpFJKr.png