14181: 【原4181】填字游戏

题目描述

author: 侯不会 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4181

Description

1.每行由自然数\(1~m\)填满，每行中每个数字用且只能用一次
2.相邻的自然数不会出现在相邻的方格中，包括左右相邻和上下相邻
3.第\(i\)列的得分为第\(i\)列所有自然数的总和\( * i\)，总得分为\(m\)列得分之和

Sample Input

``````2 5
1 3 0 2 0
4 0 3 5 2
``````

Sample Output

``````95
``````

zqy2018's solution

``````#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}

int n, m;
int lst[5041][7], tot;
bool ok[650][650] = {0};
int f[10][650];
void init(){
tot = 0;
int tmp[10];
REP(i, 0, m - 1)
tmp[i] = i + 1;
do{
bool flag = true;
REP(i, 1, m - 1){
if (abs(tmp[i] - tmp[i - 1]) == 1){
flag = false;
break;
}
}
if (flag){
++tot;
REP(i, 0, m - 1)
lst[tot][i] = tmp[i];
}
}while (next_permutation(tmp, tmp + m));
REP(i, 1, tot)
REP(j, i, tot){
ok[i][j] = ok[j][i] = true;
REP(k, 0, m - 1){
if (abs(lst[i][k] - lst[j][k]) == 1){
ok[i][j] = ok[j][i] = false;
break;
}
}
}
}
void solve(){
int tmp[10], ans = 0;
REP(i, 0, m - 1)
REP(i, 1, tot){
bool flag = true;
int res = 0;
REP(j, 0, m - 1){
if (tmp[j] != lst[i][j] && tmp[j]){
flag = false;
break;
}
res += lst[i][j] * (j + 1);
}
if (flag) f[1][i] = res;
else f[1][i] = -1;
}
REP(i, 2, n){
REP(j, 0, m - 1)
REP(j, 1, tot){
f[i][j] = -1;
REP(t, 1, tot){
if (!ok[j][t] || f[i - 1][t] < 0) continue;
bool flag = true;
int res = 0;
REP(u, 0, m - 1){
if (tmp[u] != lst[j][u] && tmp[u]){
flag = false;
break;
}
res += lst[j][u] * (u + 1);
}
if (flag)
f[i][j] = max(f[i][j], f[i - 1][t] + res);
}
ans = max(ans, f[i][j]);
}
}
printf("%d\n", ans);
}
int main(){
init();
solve();
return 0;
}
``````