hdu 2125 Local area network
1570 ワード
1.テーマ
http://acm.hdu.edu.cn/showproblem.php?pid=2125
2.分析
2 D階段のような問題は、欠陥点の問題を処理する必要があるだけです.欠陥点の横縦座標の標識に注意し、当然の自分の感覚を考えてはいけない.動的計画で使用される決定:左と下の数値の和;
3.複雑度
空間複雑度O(MN);時間複雑度O(MN);
4.関連内容
アルゴリズムアルゴリズム:ダイナミックプランニングダイナミックプランニング
5.感想
2次元の階段の問題のように、いくつかの経典のテーマを繰り返して、自分の感覚を育成する必要があると感じています.
6.コード
7.参考文献
http://acm.hdu.edu.cn/showproblem.php?pid=2125
2.分析
2 D階段のような問題は、欠陥点の問題を処理する必要があるだけです.欠陥点の横縦座標の標識に注意し、当然の自分の感覚を考えてはいけない.動的計画で使用される決定:左と下の数値の和;
3.複雑度
空間複雑度O(MN);時間複雑度O(MN);
4.関連内容
アルゴリズムアルゴリズム:ダイナミックプランニングダイナミックプランニング
5.感想
2次元の階段の問題のように、いくつかの経典のテーマを繰り返して、自分の感覚を育成する必要があると感じています.
6.コード
#include <iostream>
using namespace std;
long f2125[40][40];
void init2125(int n,int m,int &x1,int &y1,int &x2,int &y2)
{
int tempxy;
if(x1==x2 && y1>y2) { tempxy=y1; y1=y2; y2=tempxy; }
else if(y1==y2 && x1>x2) { tempxy=x1; x1=x2; x2=tempxy; }
memset(f2125,0,sizeof(f2125));
f2125[0][0]=1;
for(int i=1;i<n;++i)//
{
f2125[i][0]=f2125[i-1][0];
if(i==x2 && y2==0 && i-1==x1 && y1==0) f2125[i][0]=0;
}
for(int j=1;j<m;++j)//
{
f2125[0][j]=f2125[0][j-1];
if(0==x2 && y2==j && j-1==y1 && x1==0) f2125[0][j]=0;
}
}
int main()
{
//freopen("in.txt","r",stdin);
int n,m,x1,y1,x2,y2;
while(cin>>n>>m)
{
cin>>x1>>y1>>x2>>y2;
init2125(n,m,y1,x1,y2,x2);
for(int i=1;i<n;++i)//
for(int j=1;j<m;++j)//
{
if(i==y2 && i-1==y1 && x1==j && x2==j) f2125[i][j]=f2125[i][j-1];
else if(i==y2 && i==y1 && x1==j-1 && x2==j) f2125[i][j]=f2125[i-1][j];
else f2125[i][j]=f2125[i-1][j]+f2125[i][j-1];
}
cout<<f2125[n-1][m-1]<<endl;
}
return 0;
}
7.参考文献