Koios1143的筆記

codeforces 543A

發表於 分類於

codeforces 543A

題敘

今天有 $n$ 個程式設計師，要寫 $m$ 行程式碼
第 $i$ 個程式設計師每寫1行分別會有 $bug[i]$ 個bug
給定 $n$ $m$ $b$ $p$ $bug[]$
要求在總共不超過 $b$ 個bug的情況下， $n$ 個程式設計師完成 $m$ 行程式碼的方法數有多少種
由於結果可能很大，求總和模 $p$ 的值

想法

觀察題目後，可以發現到會影響到bug總數的會是 哪個程式設計師 以及 寫了幾行

定義

$dp[i][j][k]$ 表示第 $i$ 個程式設計師寫了 $j$ 行code後bug總數為 $k$ 的方法數

可以得到轉移式

$dp[i][j][k] = $$\Sigma_{l=0}^{j} dp[i-1][j-l][k-bug[i]*l]$$ $mod p$

做到這邊可以得到正確的解，但是估計一下時間複雜度
每個狀態要以 $O(m)$ 的時間處理
又我們有 $nmb$ 種狀態，總時間複雜度為 $O(nm^2b)$
顯然這樣的時間是不行的

我們希望我們能在 $O(1)$ 的時間完成一個狀態
觀察我們的轉移式，以 $dp[3][2][4]$ 和 $dp[3][1][2]$ 為例，並假設所有人的$bug[i]$都是2

$dp[3][2][4] = dp[2][2][4] + dp[2][1][2] + dp[2][0][0]$

$dp[3][1][2] = dp[2][1][2] + dp[2][0][0]$

可以發現到，中間只差了 $dp[2][2][4]$
也就是說

$dp[i][j][k] = dp[i][j-1][k-bug[i]] + dp[i-1][j][k]$

透過這樣的方式，可以得到一個時間複雜度為 $O(nmb)$ 的好做法
不過傳到codeforces出現compile error，空間使用量過大

再次觀察上面的轉移式，可以發現到我們的 $i$ 只跟 $i$ 和 $i-1$ 有關，也就是說，我們只需要儲存兩個就可以表達全部

$dp[i][j][k] = dp[i][j-1][k-bug[i]] + dp[!(i%2)][j][k]$

如此一來就完成了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//By Koios1143
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int dp[2][510][510]={1},bug[510],n,m,b,mod,ans=0;
int main(){
	cin>>n>>m>>b>>mod;
	for(int i=1 ; i<=n ; i++){
		cin>>bug[i];
	}
	for(int i=1 ; i<=n ; i++){
		for(int j=0 ; j<=m ; j++){
			for(int k=0 ; k<=b ; k++){
				if(j && k>=bug[i]) dp[i%2][j][k] = (dp[i%2][j-1][k-bug[i]] + dp[!(i%2)][j][k])%mod;
				else dp[i%2][j][k] = dp[!(i%2)][j][k];
				if(i==n && j==m) ans=(ans+dp[i%2][j][k])%mod;
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

複雜度

有 $nmb$ 種狀態，每種狀態轉移複雜度為 $O(1)$
總複雜度 $O(nmb)$