Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贴个c++代码 h=10,w=11时答案是3852472573499

Posted by a280920481 at 2018-11-27 20:59:52 on Problem 2411 and last updated at 2018-11-27 21:05:47
#include <iostream>
using namespace std;


long long dp[2][2048];

int main()
{
	int h, w;
	long long res;
	bool n;

	while (true)
	{
		cin >> h >> w;
		if (!h)
		{
			break;
		}

		n = false;
		for (int i = 0; i < 2048; i++)
		{
			dp[0][i] = 0;
			dp[1][i] = 0;
		}

		dp[n][0] = 1;

		for (int i = h - 1; i >= 0; i--)
		{
			for (int j = w - 1; j >= 0; j--)
			{
				for (int u = 0; u < (1 << w); u++)
				{
					res = 0;
					if ((u >> j) & true)
					{
						res = dp[n][u & (~(1 << j))];
					}
					else
					{
						if (j + 1 < w && !((u >> (j + 1)) & true))
						{
							res += dp[n][u | (1 << (j + 1))];
						}
						if (i + 1 < h)
						{
							res += dp[n][u | (1 << j)];
						}
					}
					dp[!n][u] = res;
				}
				n = !n;
			}
		}
		cout << dp[n][0] << '\n';
	}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator