AOJ 0537 Bingo
問題ページ ビンゴ | Aizu Online Judge
考えたこと
N2要素で要素の値は1以上M以下、要素の合計がSの狭義単調増加な数列が何通りあるか求めればいい。
dp[i][j][k] = (i番目までで最大の要素がjで合計がkの数列の通り数) としてDPしようとしたが遷移のうまい方法がわからず悩む。dpの要素数の時点でO(MSN2)で遷移はO(1)でできないとだめそう。累積和を持っておくDPだったり色々考えても思い浮かばない。
結局わからず解説を見ると、ループの順番をうまいことやると普通にO(MSN2)で解ける。
学び
ループの順番を頑張るとうまくDPできることがある。他の問題にも応用できそうだし覚えておきたい。
//#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 100000; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int dp[50][3010]; signed main(void) { while(true) { int n, m, s; cin >> n >> m >> s; if(!n) break; n *= n; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; // 数列中の最大の要素がi FOR(i, 1, m+1) { // j番目までで合計がkのとき何通りか for(int j=n; j>=1; --j) FOR(k, i, s+1) { (dp[j][k] += dp[j-1][k-i]) %= MOD; } } cout << dp[n][s] << endl; } return 0; }