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

## 《挑战程序设计竞赛》的解法，复杂度nm2^m

Posted by Ioencgc at 2023-07-21 12:19:57 on Problem 2411
```算法：轮廓线dp

#include<iostream>
#include<stack>
#include<string.h>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<climits>
#include<cstdio>
#include<vector>
#include<sstream>
#include<ctype.h>
#include<set>
#include<map>
#include<ctime>
#include<stdlib.h>
#include<queue>
#include<bitset>
#define ll long long
#define inf INT_MAX
using namespace std;
template<typename TTT>inline void mr(TTT& theNumberToRead)
{
theNumberToRead = 0;
bool prn = false;
char c = getchar();
while (!isdigit(c))
{
if (c == '-')prn = true;
c = getchar();
}
while (isdigit(c))
theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar();
if (prn)
theNumberToRead = -theNumberToRead;
}
template<typename TTT>inline TTT mrr()
{
TTT theNumberToRead = 0;
bool prn = false;
char c = getchar();
while (!isdigit(c))
{
if (c == '-')prn = true;
c = getchar();
}
while (isdigit(c))
theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar();
return prn ? -theNumberToRead : theNumberToRead;
}
template<typename T>void my_write(T x)
{
if (x)
my_write(x / 10),
putchar(x % 10 ^ 48);
}
template<typename T>void mw(T x, char mid)
{
if (x)
{
if (x < 0)
putchar('-'),
x = -x;
my_write(x);
}
else putchar(48);
if (mid)
putchar(mid);
}
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
// ******************************************华丽的分割线******************************************
ll dp[2][1 << 11];
int main()
{
int n, m;
while (mr(n), mr(m), n)
{
if (n < m)
swap(n, m);
memset(dp[0], 0, sizeof(dp));
ll* crt = dp[0], * nex = dp[1];
crt[0] = 1;
for(int i=n-1; ~i; --i)
for (int j = m - 1; ~j; --j)
{
for (int k = 0; k < 1 << m; ++k)
{
if (k & 1 << j)
nex[k] = crt[k ^ 1 << j];
else
{
nex[k] = 0;
if (j + 1 < m && !(k & 1 << j + 1))
nex[k] += crt[k | 1 << j + 1];
if (i + 1 < n)
nex[k] += crt[k | 1 << j];
}
}
swap(crt, nex);
}
mw(crt[0], '\n');
}
return 0;
}```

Followed by:

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

Content:

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