QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #786719 | #9802. Light Up the Grid | solunar | WA | 26ms | 3944kb | C++11 | 2.1kb | 2024-11-26 23:03:04 | 2024-11-26 23:03:04 |
Judging History
answer
// 2024ICPCShenyangE
#include <iostream>
#include <algorithm>
using namespace std;
#include <math.h>
#include <memory.h>
int m;
char ope[9] = {15, 10, 5, 12, 3, 8, 4, 2, 1};//{1, 2, 4, 8, 3, 12, 5, 10, 15 }; // 9种操作
int a[9]; // 操作的代价
int grid;
int dp[1<<16]; // dp[i]: 状态i是格子集合的位串表示
int memoir(int s) {
// s必不含全1格(1<<15)
if (dp[s] >= 0)
return dp[s];
if (s == 0)
return dp[s] = 0;
dp[s] = 2e9;
for (int i = 0; i < 9; i++) {
int newst = 0;
for (int j = 0; j < 16; j++)
if ((s & (1 << j)) && ((j ^ ope[i]) != 15))
newst |= (1 << (j ^ ope[i]));
int suba = memoir(newst);
dp[s] = min(dp[s], a[i] + suba);
}
return dp[s];
}
int main() {
int t, a0, a1, a2, a3;
char ch;
ios::sync_with_stdio(false);
cin >> t >> a0 >> a1 >> a2 >> a3;
a[8] = a[7] = a[6] = a[5] = a0;
a[4] = a[3] = a1;
a[2] = a[1] = a2;
a[0] = a3;
for (int i = 0; i < (1 << 16); i++)
dp[i] = -1;
while (t--) {
cin >> m;
int st = 0;
for (int i = 0; i < m; i++) {
grid = 0;
for (int j = 0; j < 4; j++) {
cin >> ch;
if (ch == '1')
grid |= (1 << j);
}
st |= (1 << grid);
}
if (st & (1 << 15)) { // 含全1格
int ans = 2e9;
for (int i = 0; i < 9; i++) {
int newst = 0;
for (int j = 0; j < 16; j++)
if ((st & (1 << j)) && ((j ^ ope[i]) != 15))
newst |= (1 << (j ^ ope[i]));
ans = min(ans, a[i] + memoir(newst));
}
cout << ans << endl;
} else
cout << memoir(st) << endl;
}
return 0;
}
/*
4 8 2 7 8
8
0001
0011
0010
1111
1010
0110
0100
1011
8
1101
1100
0110
1111
0001
0101
0100
1110
9
0000
0101
1011
0001
1110
1100
1111
0011
0110
9
1111
1000
1100
1101
0010
0111
0001
0101
1001
34
32
38
36
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3944kb
input:
2 1000 100 10 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
1121 2
result:
ok 2 number(s): "1121 2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
2 1 1 1 1 4 10 00 01 00 00 10 00 01 1 11 11
output:
5 2
result:
ok 2 number(s): "5 2"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
1 1000000 1000000 1000000 1000000 1 11 11
output:
2000000
result:
ok 1 number(s): "2000000"
Test #4:
score: -100
Wrong Answer
time: 26ms
memory: 3844kb
input:
10000 8 2 7 8 8 00 01 00 11 00 10 11 11 10 10 01 10 01 00 10 11 8 11 01 11 00 01 10 11 11 00 01 01 01 01 00 11 10 9 00 00 01 01 10 11 00 01 11 10 11 00 11 11 00 11 01 10 9 11 11 10 00 11 00 11 01 00 10 01 11 00 01 01 01 10 01 11 00 01 01 01 10 10 00 11 11 11 11 10 ...
output:
34 32 38 36 40 36 42 38 44 41 37 44 37 37 37 32 29 39 39 44 38 39 44 37 29 37 38 38 34 34 32 45 34 36 41 41 44 34 37 34 29 36 39 44 42 35 40 37 38 38 41 29 40 41 36 41 43 44 42 34 42 39 38 33 34 38 38 37 42 40 34 36 28 34 32 38 36 40 39 37 36 38 34 34 34 35 42 41 38 38 44 40 37 40 38 29 36 40 36 34 ...
result:
wrong answer 3rd numbers differ - expected: '36', found: '38'