2buttonsのeiya解
https://hoj.hamako-ths.ed.jp/onlinejudge/contest/121/problems/5
提出しても見られないみたいなのではるだけはっておきます。
ところで通常問題の方のURLをはりたかったのですが、なんかidがずれるみたいなのではりません。
現時点(2017/12/2)ではidは869です。
部分点(20点)
#if 1 #include <iostream> #include <fstream> #include <string> #include <vector> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <queue> #include <stack> #include <array> #include <deque> #include <algorithm> #include <utility> #include <cstdint> #include <functional> #include <iomanip> #include <numeric> #include <assert.h> #include <bitset> #include <list> auto& in = std::cin; auto& out = std::cout; int32_t H,W; int32_t ah,aw,bh,bw; int32_t map[1000][1000]; int32_t distA(int32_t h, int32_t w) { return std::abs(h - ah) + std::abs(w - aw); } int32_t distB(int32_t h, int32_t w) { return std::abs(h - bh) + std::abs(w - bw); } int64_t func(int32_t i, int32_t j, bool myturn)//Aがtrue、先行がtrue { bool finish = true; for (int32_t h = 0; h < H; h++) for (int32_t w = 0; w < W; w++) { if (distA(h, w) >= i && distB(h, w) >= j) { finish = false; } } if (finish) { return 0; } auto pattA = func(i + 1, j, !myturn); if(myturn) for (int32_t h = 0; h < H; h++) for (int32_t w = 0; w < W; w++) { if (distA(h, w) == i && distB(h, w) >= j) { pattA += map[h][w]; } } auto pattB = func(i, j + 1, !myturn); if (myturn) for (int32_t h = 0; h < H; h++) for (int32_t w = 0; w < W; w++) { if (distA(h, w) >= i && distB(h, w) == j) { pattB += map[h][w]; } } if (myturn == (pattA>pattB)) { return pattA; } else { return pattB; } } int main() { using std::endl; in.sync_with_stdio(false); out.sync_with_stdio(false); in.tie(nullptr); out.tie(nullptr); in >> H>>W; in >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw; for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) { in >> map[h][w]; } out << func(0, 0, true) << endl;; return 0; } #endif
満点
#include <iostream> #include <cstdint> #include <algorithm> int32_t H, W; int32_t ah, aw; int32_t bh, bw; int32_t map[1000][1000]; const int32_t DIST_MAX = 2000; int64_t scoreA[DIST_MAX+2][DIST_MAX+2];//自分、相手 int64_t scoreB[DIST_MAX+2][DIST_MAX+2];//自分、相手 const int64_t INF = 100010002000000000; int64_t dp[DIST_MAX + 2][DIST_MAX + 2]; int64_t func(int32_t a, int32_t b) { if (a == DIST_MAX+1 && b == DIST_MAX+1) { return 0; } if (a > DIST_MAX+1 || b > DIST_MAX+1) { return INF; } if (dp[a][b] != INF) { return dp[a][b]; } return dp[a][b] = std::max( -func(a + 1, b) + scoreA[a][b], -func(a, b + 1) + scoreB[b][a] ); } int main() { using std::cin; using std::cout; using std::endl; for (auto& arr : dp)for (auto& i : arr) { i = INF; } cin >> H >> W; for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) { cin >> map[h][w]; } cin >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw; int64_t sum = 0; for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) { int32_t dist_a = std::abs(h - ah) + std::abs(w - aw); int32_t dist_b = std::abs(h - bh) + std::abs(w - bw); scoreA[dist_a][dist_b] += map[h][w]; scoreB[dist_b][dist_a] += map[h][w]; sum += map[h][w]; } for (int32_t distme = 0; distme <= DIST_MAX; ++distme) { for (int32_t distopp = DIST_MAX-1; distopp >= 0; --distopp) { scoreA[distme][distopp] += scoreA[distme][distopp + 1]; scoreB[distme][distopp] += scoreB[distme][distopp + 1]; } } cout << (func(0, 0)+ sum)/2 << endl; }