QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631865#517. Sequential Yahtzeechuchu#WA 121ms3860kbC++204.2kb2024-10-12 10:42:282024-10-12 10:42:28

Judging History

你现在查看的是最新测评结果

  • [2024-10-12 10:42:28]
  • 评测
  • 测评结果:WA
  • 用时:121ms
  • 内存:3860kb
  • [2024-10-12 10:42:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf = 1e9;

void solve() {
    int n; cin >> n;
    vector<int> a(n); for(auto& x : a) cin >> x;
    vector<vector<int>> dp(13, vector<int>(n+1, 0)); //dp[cat][i] = best score i can get if i start round cat at card i

    auto score = [&] (int cat, vector<int> cand) {
        assert(cand.size() == 5);
        sort(cand.begin(), cand.end()); //sort candidate vector
        int sum = accumulate(cand.begin(), cand.end(), 0);
        if (cat <= 6) { // 1 - 6
            int ct = 0;
            for (auto x : cand) 
                if (x == cat) ct++;
            return ct * cat;
        }
        if (cat == 7) { // triple
            for (int i = 0; i < 3; ++i) {
                if (cand[i] == cand[i+2]) return sum;
            }
            return 0;
        }
        if (cat == 8) { // quadruple
            for (int i = 0; i < 2; ++i) {
                if (cand[i] == cand[i+3]) return sum;
            }
            return 0;
        }
        if (cat == 9) { // full house
            if (cand[0] == cand[2] && cand[2] != cand[3] && cand[3] == cand[4]) return 25;
            if (cand[0] == cand[1] && cand[1] != cand[2] && cand[2] == cand[4]) return 25;
            return 0;
        }
        if (cat == 10) { // short straight
            for (int i = 0; i < 2; ++i) {
                int tmp = cand[i];
                for (int j = i+1; j < i+5; ++j) {
                    if (j == i+4) return 30;
                    if (cand[j] != tmp + 1) break;
                    tmp++;
                }
            }
            return 0;
        }
        if (cat == 11) { // long straight
            int tmp = cand[0];
            for (int j = 1; j < 6; ++j) {
                if (j == 5) return 40;
                if (cand[j] != tmp+1) break;
                tmp++;
            }
            return 0;
        }
        if (cat == 12) { // chance
            return sum;
        } 
        if (cat == 13) { // yahtzee
            if (cand[0] == cand[4])
                return 50;
            return 0;
        }
        assert(false);
        return 0;
    };

    // iterate cats
    for (int cat = 12; cat >= 0; --cat) {
        // iterate start pos
        for (int i = 0; i < n-4; ++i) {
            // generate candidate hands
            vector<int> cand(5);
            for (int j = 0; j < 5; ++j) cand[j] = a[i+j];
            vector<int> sv = cand, sv2;

            // some flag that doesn't work
            bool ok = 1;
            // iterate bitmask for things to swap out
            for (int j = 0; j < 32; ++j) {
                ok = 1;
                // restore old candidate
                cand = sv;
                // track next replacement dice roll
                int tmp = i+5;
                // fix each dice
                for (int k = 0; k < 5; ++k) {
                    if ((j >> k) & 1) {
                        if (tmp == n) { ok = 0; break; }
                        cand[k] = a[tmp++];
                    }
                }
                if (!ok) continue;

                // save old candidate so we don't stack changes basically
                // then do the same thing but with tmp2 (2nd swap round)
                sv2 = cand;
                for (int k = 0; k < 32; ++k) {
                    ok = 1;
                    cand = sv2;
                    int tmp2 = tmp;
                    for (int l = 0; l < 5; ++l) {
                        if ((k >> l) & 1) {
                            if (tmp2 == n) { ok = 0; break; }
                            cand[l] = a[tmp2++];
                        }
                    }
                    if (!ok) continue;

                    // update dp
                    dp[cat][i] = max(dp[cat][i], score(cat + 1, cand) + (cat == 12 ? 0 : dp[cat+1][tmp2]));
                }
            }
        }
    }

    int ans = -inf;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, dp[0][i]);
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);

	int t = 1;
    // cin >> t;
	while (t--) solve();
}

详细

Test #1:

score: 100
Accepted
time: 22ms
memory: 3624kb

input:

65
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1

output:

70

result:

ok single line: '70'

Test #2:

score: 0
Accepted
time: 45ms
memory: 3556kb

input:

76
3 1 1 1 1 1 4 2 5 2 6 1 3 5 2 2 2
3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 1 1 1 2 2 1 2 3 4 5
1 2 3 4 5 1 1 6 1 6 6 6 6 1 1 1 1 1 4

output:

340

result:

ok single line: '340'

Test #3:

score: 0
Accepted
time: 82ms
memory: 3640kb

input:

195
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 ...

output:

70

result:

ok single line: '70'

Test #4:

score: 0
Accepted
time: 26ms
memory: 3652kb

input:

65
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1

output:

70

result:

ok single line: '70'

Test #5:

score: 0
Accepted
time: 27ms
memory: 3560kb

input:

66
2 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1

output:

70

result:

ok single line: '70'

Test #6:

score: 0
Accepted
time: 119ms
memory: 3632kb

input:

195
2 2 2 2 2
3 3 3 3 3
1 1 1 1 1
1 1 1 1 1
3 3 3 3 3
2 2 2 2 2
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
1 1 1 1 1
2 2 2 2 2
4 4 4 4 4
1 1 1 1 1
2 2 2 2 2
5 5 5 5 5
1 1 1 1 1
2 2 2 2 2
6 6 6 6 6
1 1 1 1 1
2 2 2 2 2
6 6 6 6 6
1 1 1 1 1
2 2 2 2 2
6 6 6 6 6
1 2 3 4 5
2 3 4 5 6
1 2 1 2 1
1 1 1 1 1
2 2 2 2 2
1 6 4 ...

output:

340

result:

ok single line: '340'

Test #7:

score: 0
Accepted
time: 121ms
memory: 3856kb

input:

195
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
2 2 2 2 2
1 1 1 1 1
3 3 3 3 3
3 3 3 3 3
2 2 2 2 2
1 1 1 1 1
4 4 4 4 4
3 3 3 3 3
2 2 2 2 2
5 5 5 5 5
4 4 4 4 4
3 3 3 3 3
6 6 6 6 6
5 5 5 5 5
4 4 4 4 4
6 6 6 6 6
1 2 3 4 5
2 3 4 5 6
6 6 6 6 6
1 2 3 4 5
5 5 5 5 5
1 1 1 2 2
1 2 3 4 4
2 2 3 4 6
2 2 3 4 5
1 1 1 1 1
1 1 1 ...

output:

340

result:

ok single line: '340'

Test #8:

score: 0
Accepted
time: 81ms
memory: 3508kb

input:

135
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
1 2 2 2 3
1 2 3 4 5
6 6 6 5 5
6 6 6 6 6
1 2 3 4 5
5 5 5 5 5
1 1 1 2 2
1 2 3 4 4
2 2 3 4 6
2 2 3 4 5
1 1 1 1 1
1 1 1 1 1
6 5 4 3 2
1 1 1 1 1
1 1 1 1 1
6 6 6 6 6
6 6 5 5 4
6 5 4 3 2
6 6 6 6 6
1 2 3 4 5
1 1 1 2 3

output:

338

result:

ok single line: '338'

Test #9:

score: 0
Accepted
time: 49ms
memory: 3560kb

input:

85
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
6 6 6 6 6
6 6 6 6 6
1 1 1 2 2
1 2 3 4 4
1 2 3 4 5
6 6 6 6 6
1 1 1 1 1

output:

322

result:

ok single line: '322'

Test #10:

score: 0
Accepted
time: 49ms
memory: 3860kb

input:

77
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
1 1 1 2 2
2 2 2 2 3
1 1 1 1 3
2 2 4 4 5
1 1 3 3 6
6 5 4 1 2
3 4 5 4 3 2 1
2 2 3 3 4
1 1 2 2 3

output:

237

result:

ok single line: '237'

Test #11:

score: 0
Accepted
time: 109ms
memory: 3596kb

input:

180
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
3 3 3 3 3
3 3 3 3 3
3 3 3 3 3
4 4 4 4 4
4 4 4 4 4
4 4 4 4 4
5 5 5 5 5
5 5 5 5 5
5 5 5 5 5
6 6 6 6 6
6 6 6 6 6
6 6 6 6 6
1 1 2 2 3
6 5 4 3 2
4 2 1 3 6
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 4 5 6 1
3 4 5 6 1
3 4 5 6 1
4 5 6 1 2
4 5 6 1 2
4 5 6 1 2
5 6 1 2 3
5 6 1 2 3
5 6 1 ...

output:

294

result:

ok single line: '294'

Test #12:

score: -100
Wrong Answer
time: 35ms
memory: 3564kb

input:

65
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
1 1 1 1 1
1 2 3 4 5
1 2 3 4 5
1 1 2 2 3
1 1 1 1 1
2 2 2 2 2
1 1 1 1 1
1 1 1 1 2

output:

52

result:

wrong answer 1st lines differ - expected: '5', found: '52'