首页 > ACM题库 > HDU-杭电 > hdu 2125 Local area network-动态规划-[解题报告]C++
2013
12-29

hdu 2125 Local area network-动态规划-[解题报告]C++

Local area network

问题描述 :

A local area network (LAN) supplies networking capability to a group of computers in close proximity to each other such as in an office building, a school, or a home. A LAN is useful for sharing resources like files, printers, games or other applications. A LAN in turn often connects to other LANs, and to the Internet or other WAN.
In this contest, everybody is connecting with each others like the following figure.

The contest’s network was built as N rows and M columns, your computer locate at (0, 0) and the judger’s computer locate at (m-1, n-1) The code you submit would only transfer to up or right smoothly. It doesn’t matter if some accidents happened. Could you tell me how many ways from your computer to judger when a data wire was broken?

输入:

There are multiple cases. Every case contains two integers in the first line, N, M (3<=N+M<=40). Second line contains four integers X1, Y1, X2, Y2 (0<=X1, X2<M, 0<=Y1, Y2<N, |X1+Y1-X2-Y2|=1), meaning the broken wire position.

输出:

There are multiple cases. Every case contains two integers in the first line, N, M (3<=N+M<=40). Second line contains four integers X1, Y1, X2, Y2 (0<=X1, X2<M, 0<=Y1, Y2<N, |X1+Y1-X2-Y2|=1), meaning the broken wire position.

样例输入:

3 3
0 0 1 0

样例输出:

3

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=40+10;
int dp[MAX][MAX];
bool mark[MAX][MAX];

int main(){
	int n,m,x1,y1,x2,y2;
	while(cin>>n>>m){
		memset(mark,false,sizeof mark);
		cin>>x1>>y1>>x2>>y2;
		dp[0][1]=1;
		mark[y1+1][x1+1]=mark[y2+1][x2+1]=true;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
				if(mark[i][j] && mark[i-1][j])dp[i][j]-=dp[i-1][j];
				if(mark[i][j] && mark[i][j-1])dp[i][j]-=dp[i][j-1];
			}
		}
		cout<<dp[n][m]<<endl;
	}
	return 0;
}

解题转自:http://blog.csdn.net/xingyeyongheng/article/details/9672933


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge