Sicily 1033 City Road (SOJ 1033)「dp动态规划」

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/30

原题地址:点击打开链接

感觉也是一题水题,不过也看了tips,啊!!!!!没办法啊,人菜,搜答案的时候我还没点进去搜索结果,看到DP我就立刻知道怎么做了····呃·····

其实动态规划我一直觉得是十分难想的题目,不过从第一次接触动态规划到现在,已经有了长足进步,继续加油吧~

———–正文————

原本想着能不能用排列组合,不过后来看到题目后就打消了,方块一多,会不好写。

这题主要需要注意的地方有:

1 数组可以开一维数组,不过要用函数对行列进行映射

2 数组大小至少是2*(1000000+1),因为这是房屋之间最大可能出现的街道交点个数

3 下标

接下来好像也没什么了,直接写就可以了,a[i,j] (代码中使用了函数映射,为a[t(i,j)])表示从原点走到这里有多少种走法,正常情况下:a[i,j]=a[i-1,j]+a[i,j-1] ,同时考虑某些点不可达的情况。

代码如下:

#include<iostream>
#include<stdio.h>
#include<memory.h>
#define MAX 2500000
using namespace std;
long long a[MAX];       //方案数 
bool hor[MAX],ver[MAX]; //hor代表从一个点出发是否可以往右走,ver则代表从一个点出发是否可以往上走 
int m,n,b,tr,tc,th,tw;  //tr=temp row-number, tc=temp column-number, th=temp height, tw=temp width
inline int t(const int &r, const int &c)  //下标映射函数,从2维转换到1维,可以不写成inline,不过慢0.6秒 ,但还是能AC 
{
    return ((n+1)*r+c);
}
int main()
{
    while(scanf("%d%d",&m,&n) && m*n!=0)
    {
        memset(a, 0, sizeof(a));
        for(int i=0;i<=m;++i)
         for(int j=0;j<=n;++j)
             hor[t(i,j)] = ver[t(i,j)] = 1;
        
        scanf("%d",&b);
        for(int i=0;i<b;++i)
        {
            scanf("%d%d%d%d",&tr,&tc,&th,&tw);
            for(int j=tr;j<(tr+th-1);++j) //hor
                for(int k=tc-1;k<(tc+tw-1);++k)
                    hor[t(j,k)]=0;
            for(int j=(tr-1);j<(tr+th-1);++j) //ver
                for(int k=tc;k<(tc+tw-1);++k)
                    ver[t(j,k)]=0;
        }

        for(int i=0;i<=m;++i) a[t(i,0)]=1;
        for(int i=0;i<=n;++i) a[t(0,i)]=1;
        for(int i=1;i<=m;++i)
            for(int j=1;j<=n;++j)
            {
                if(hor[t(i,j-1)])
                    a[t(i,j)]+=a[t(i,j-1)];
                if(ver[t(i-1,j)])
                    a[t(i,j)]+=a[t(i-1,j)];
            }
        printf("%lld\n",a[t(m,n)]);
    }
}                                 

发表评论

电子邮件地址不会被公开。 必填项已用*标注