ACM ：漫漫上学路 -DP -水题

CSU 1772 漫漫上学路

Time Limit: 1000MS

Memory Limit: 131072KB

64bit IO Format: %lld & %llu

Submit Status

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

4

Sample Output

14

Hint

14条最短路线如下

Source

csuxushu

开学了，一大堆的事情，，，好久都没刷题了，找到dp专题试试手。

dp水题，状态转移方程为 :

maps[i][j] = j==?maps[i-][j]:(j==i?maps[i][j-]:maps[i][j-]+maps[i-][j])

二重for循环：

AC代码：

#include"algorithm"

#include"iostream"

#include"cstring"

#include"cstdio"

using namespace std;

typedef long long LL ;

#define memset(x,y) memset(x,y,sizeof(x))

LL maps[50][50];

int main()

{

    int n;

    while(cin>>n)

    {

        memset(maps,0);

        maps[0][0]=1;

        for(int i=1; i<=n; i++)

        {

            for(int j=0; j<=i; j++)

            {

                maps[i][j] = j==0?maps[i-1][j]:(j==i?maps[i][j-1]:maps[i][j-1]+maps[i-1][j]);

            }

        }

        cout<<maps[n][n]<<endl;

    }

    return 0;

}