2013-07-12 13:31:17Morris
[UVA][dp] 11133 - Eigensequence
Problem E: Eigensequence
Given an increasing sequence of integers a1, a2, a3, ..., ak, the E-transform produces a sequence of the same length, b1, b2, b3, ..., bk such that- b1 = a1
- for j>1, bj is the only integer aj-1 < bj ≤ aj, which is divisible by aj - aj-1.
A sequence S such that E(S)=S is called an eigensequence. For instance, S = 2,3,4,6,8,12,16,18,20 is an eigensequence.
Given integers a1 and an, how many eigensequences (of any length) start with a1 and end with an?
Input has many data lines, followed by a terminating line. Each line has two integers, a1 and an. If a1 < an, it's a data line. Otherwise it's a terminating line that should not be processed. On each line, 0 ≤ a1 ≤ an ≤ 44. This guarantees that each output fits into 32 bit integer.
For each data line, print a line with a1, an, and x, where x is the number of eigensequences (of any length) that start with a1 and end with an.
Sample input
0 3 5 7 2 8 0 0
Output for sample input
0 3 3 5 7 1 2 8 12
Don Reble
題目是要找到 E(S) = S 的個數為何，起點是 a1 終點是 an。
我們決定使用動態規劃去進行計算
dp[i][j] 表示當前長度為 i, bi 的值為 j 的方法數。
由於限定 E(S) = S, ai = bi, 且 bi 遞增, ai 遞增。
轉移的方式窮舉下一個可以變成的 bi 為何。
#include <stdio.h>
#include <string.h>
int dp[50][50];//[length][bi]
int main() {
int a1, an;
int i, j, k, l, p;
while(scanf("%d %d", &a1, &an) == 2) {
if(a1 == 0 && an == 0) break;
memset(dp, 0, sizeof(dp));
dp[1][a1] = 1;
int ret = 0;
for(i = 1; i <= an+1; i++) {
ret += dp[i][an];
for(j = 0; j <= an; j++) {
if(dp[i][j] == 0) continue;
for(l = j+1; l <= an; l++) {//next ai
int v = l-j;
if(l%v == 0)
dp[i+1][l] += dp[i][j];
}
}
}
printf("%d %d %d\n", a1, an, ret);
}
return 0;
}