【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a830
【解題想法】DP
- 此系統假設實驗一開始有M個成熟的超級細菌及N個新生的超級細菌
- 一個新生的超級細菌a必須經過X+Y分鐘後才能第一次繁衍新生的超級細菌a
- 經過X分鐘後，長成為成熟超級細菌a。
- 再經過Y分鐘後，才能第一次開始繁衍新生的超級細菌a。
- newN[i]: 第 i 天新增的新生超級細菌數目。第 i – Y, i – 2Y …天的成熟超級細菌數目總和，乘以 Z。
- newM[i]: 第 i 天新增的成熟超級細菌數目。等於第 i – X 天的新生超級細菌數目。
- 「新生」超級細菌一旦變成「成熟」超級細菌，要從新生超級細菌數目被扣除。
#include <iostream>
using namespace std;
const int maxn = 105;
int newM[maxn];
int newN[maxn];
int main() {
int M, N, W, X, Y, Z;
cin >> M >> N >> W >> X >> Y >> Z;
int sumM = M;
int sumN = N;
newM[0] = M;
newN[0] = N;
for (int i=1; i<=W; i++){
int tmp = 0;
for (int j=i-Y; j>=0; j-=Y){
tmp += newM[j];
}
newN[i] = tmp * Z;
sumN += newN[i];
if (i - X >= 0){
newM[i] = newN[i-X];
sumM += newM[i];
sumN -= newN[i-X];
newN[i-X] = 0;
}
}
cout << sumN + sumM << "\n";
return 0;
}
Python code (credit: Amy Chou)
M, N, W, X, Y, Z = map(int, input().split())
sumM = M
sumN = N
newM = [M] + [0 for _ in range(W)]
newN = [N] + [0 for _ in range(W)]
for i in range(1, W+1):
tmp = 0
for j in range(i-Y, -1, -Y):
tmp += newM[j]
newN[i] = tmp * Z
sumN += newN[i]
if i - X >= 0:
newM[i] = newN[i - X]
sumM += newM[i]
sumN -= newN[i - X]
newN[i - X] = 0
print(sumN + sumM)