JOI 2012-2013 本選 問題1 電飾
反転回数は最大でも1回かと思っていたけど2回だった。反省
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 前回反転させた, 前回のランプ, 場所 int dp[3][2][100001]; int main() { int n, k, ans = 0; vector<bool> a; cin >> n; for(int i = 0; i < n; i++) { cin >> k; a.push_back(k); } dp[0][a[0]][0] = dp[1][!a[0]][0] = 1; for(int i = 1; i < n; i++) { dp[0][a[i]][i] = max(dp[0][a[i]][i], dp[0][!a[i]][i-1] + 1); dp[1][!a[i]][i] = max(dp[1][!a[i]][i], dp[1][a[i]][i-1] + 1); dp[1][!a[i]][i] = max(dp[1][!a[i]][i], dp[0][a[i]][i-1] + 1); dp[2][a[i]][i] = max(dp[2][a[i]][i], dp[2][!a[i]][i-1] + 1); dp[2][a[i]][i] = max(dp[2][a[i]][i], dp[1][!a[i]][i-1] + 1); ans = max(ans, dp[0][a[i]][i]); ans = max(ans, dp[1][!a[i]][i]); ans = max(ans, dp[2][a[i]][i]); } cout << ans << endl; }
JOI 2013-2014 予選4番
最近forで回すDPの方が書きやすい、と感じている
最初、鍵を持っている人の情報を持ってしまっていて重複したケースも数え上げてしまっていて時間が結構かかった。
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <algorithm> using namespace std; const int MOD = 10007; // J = 0bit, O = 1bit, I = 2bit // i日目, 参加した人(bit表現) int dp[1001][12]; int main() { map<char, int> D; D['J'] = 0, D['O'] = 1, D['I'] = 2; int N, ans = 0; string S; cin >> N >> S; for(int i = 0; i < 1 << 3; i++) { if(((i >> D[S[0]]) & 1) && ((i >> D['J']) & 1)) { dp[0][i] = 1; } } for(int i = 1; i < N; i++) { for(int j = 0; j < 1 << 3; j++) { for(int k = 0; k < 1 << 3; k++) { for(int l = 0; l < 3; l++) { if((k >> D[S[i]] & 1) && ((k >> l) & 1) && ((j >> l) & 1)) { dp[i][k] += dp[i-1][j]; dp[i][k] %= MOD; break; } } } } } for(int i = 0; i < 1 << 3; i++) { ans += dp[N-1][i]; ans %= MOD; } cout << ans << endl; }
PKU 1036
少し読解困難だった．
はTLEするが，
の処理は外に出すことができるため
となる．
dp[i][j] := i時間で扉がjの状態であるときに，来訪するgang達の価値の総和の最大値
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <string> #include <map> using namespace std; const int INF = 1 << 30; int dp[2][101]; int main() { int N, K, T, t[101], p[101], s[101], ans = 0; cin >> N >> K >> T; for(int i = 0; i < N; i++) { scanf("%d", &t[i]); } for(int i = 0; i < N; i++) { scanf("%d", &p[i]); } for(int i = 0; i < N; i++) { scanf("%d", &s[i]); } for(int i = 0; i < 2; i++) for(int j = 0; j <= K; j++) dp[i][j] = -INF; dp[0][0] = 0; for(int i = 1; i <= T; i++) { int n = i & 1; int c = !n; for(int j = 0; j <= K; j++) { dp[n][j] = dp[c][j]; if(j+1 <= K) dp[n][j] = max(dp[n][j], dp[c][j+1]); if(j-1 >= 0) dp[n][j] = max(dp[n][j], dp[c][j-1]); } for(int j = 0; j < N; j++) { if(i != t[j]) continue; dp[n][s[j]] += p[j]; } } for(int i = 0; i <= K; i++) { ans = max(ans, dp[T&1][i]); } cout << ans << endl; }
JMC 2014 4番
pastaっぽいと思った。作問のプロだと感じた(小並感)
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <algorithm> using namespace std; int dp[128][128][2]; bool m[128][128]; const int MOD = 100000; int main() { int N, M, L, a, b; cin >> N >> M >> L; for(int i = 0; i < L; i++) { cin >> a >> b; a--, b--; m[a][b] = true; } for(int i = 0; i < M; i++) { if(!m[0][i]) dp[0][i][0] = 1; } for(int i = 0; i < N - 1; i++) { for(int j = 0; j < M; j++) { for(int k = 0; k < 2; k++) { if(k == 0) { if(m[i + 1][j]) continue; dp[i + 1][j][!k] += dp[i][j][k]; dp[i + 1][j][!k] %= MOD; } else { for(int l = 0; l < M; l++) { if(m[i + 1][l]) continue; a = (l == j ? k : !k); dp[i + 1][l][a] += dp[i][j][k]; dp[i + 1][l][a] %= MOD; } } } } } int ans = 0; for(int i = 0; i < M; i++) { ans += dp[N - 1][i][1]; ans %= MOD; } cout << ans<< endl; }
PKU 1014
JOI予選が近づいてきて，JOI予選の過去問解いてない後輩を煽るためPKUのDP問題解いてます（意味不明）
AOJ 0271: Izua Dictionary
解説
文字列をsとして愚直にシミュレーションしていくと、sを適当に入れ替えたときのi番目(1 <= i <= n)の文字の位置を求めるのに、i番目までに使った文字が影響される。よって最初にBITで[1, n]に1を加えておき、s[i]の場所ごとにiを0にしていくことで、sum(i)でi番目の文字の位置を求めることができる。（日本語難しすぎ）
割とゴリ押しな感じあふれてる。
ソースコード
めっちゃ汚い…
typedef long long i64; const i64 MOD = 1000000007; const int MAX_N = 100002; struct BinaryIndexedTree { int data[MAX_N]; BinaryIndexedTree() { memset(data, 0, sizeof data); } // [1, n] i64 sum(i64 i) { i64 ret = 0; for(; i > 0; i -= i & -i) { ret += data[i]; } return ret; } void add(i64 i, i64 x) { for(; i < MAX_N; i += i & -i) { data[i] += x; } } }; int main() { int pair[MAX_N]; i64 ans; i64 fact[MAX_N]; fact[0] = 1; for(int i = 1; i < MAX_N; i++) { fact[i] = i * fact[i - 1]; fact[i] %= MOD; } int n, r; while(cin >> n, n) { cin >> r; ans = 0; BinaryIndexedTree b; for(int i = 0; i < MAX_N; i++) { b.add(i + 1, 1); pair[i] = i; } for(int i = 0, a, b; i < r; i++) { cin >> a >> b; swap(pair[a-1], pair[b-1]); } for(int i = 0; i < n; i++) { i64 x = b.sum(pair[i] + 1) - 1; b.add(pair[i] + 1, -1); ans += x * fact[n - i - 1]; ans %= MOD; } cout << ans << endl; } }
AOJ 0231 Dangerous Bridge
解法
高々100人の情報しかないので、座標圧縮すると最大でも200回ループ回せば終わる。
ソースコード
struct P { int m; long long a, b; }; int n, from[128], to[128], sum[128]; P p[128]; int main() { while(scanf("%d", &n) && n) { string ans = "OK"; memset(sum, 0, sizeof sum); vector<long long> x; for(int i = 0; i < n; i++) { scanf("%d%lld%lld", &(p[i].m), &(p[i].a), &(p[i].b)); x.push_back(p[i].a); x.push_back(p[i].b); } sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); for(int i = 0; i < n; i++) { from[i] = lower_bound(x.begin(), x.end(), p[i].a) - x.begin(); to[i] = lower_bound(x.begin(), x.end(), p[i].b) - x.begin(); } for(int i = 0; i < n; i++) { for(int j = from[i]; j < to[i]; j++) { sum[j] += p[i].m; } } for(int i = 0; i < x.size(); i++) { if(sum[i] > 150) { ans = "NG"; break; } } cout << ans << endl; } }
やっと300問…。部活に忙しい毎日…
