2010年02月08日星期一.sgu160 pku2206
本人WA@ test case 8了幾次，最后才發(fā)現(xiàn)原來(lái)輸出要按照序號(hào)的升序。。。
仔細(xì)讀題。。。
dp,可一維，可二維。一維的更好想，更好寫(xiě)，更快
其實(shí)如果沒(méi)有取模的運(yùn)算，完全就是一個(gè)背包的變形問(wèn)題。
看下例：一個(gè)數(shù)x，乘以y取模之后可以比x大也可能比x小
......x......
....x.....x..
所以，不論是按照x升序掃描,還是降序掃描都有可能取到當(dāng)前數(shù)產(chǎn)生的狀態(tài)。
如果寫(xiě)二維dp就沒(méi)有這個(gè)問(wèn)題了。如果要寫(xiě)成一維dp可以記錄一下這個(gè)狀態(tài)是第幾個(gè)數(shù)
產(chǎn)生的，狀態(tài)轉(zhuǎn)移的時(shí)候只處理由當(dāng)前數(shù)之前的數(shù)生成的狀態(tài)。
1
2 const int M = 1024;
3 int idx[M];
4 int pre[M];
5 int lev[M];
6 int out[M],top = 0;
7 int m,n;
8 int main()
9 {
10 int i,j,k;
11 scanf("%d%d",&n,&m);
12 pre[1] = 1;
13 lev[1] = 1;
14 for (i = 1;i <= n;i++) {
15 scanf("%d",&k);
16 for (j = 1;j <= m;j++) {
17 if (pre[j] && lev[j] <= i) {
18 int t = (j * k) % m;
19 if (!pre[t]) {
20 lev[t] = i + 1;
21 pre[t] = j;
22 idx[t] = i;
23 }
24 }
25 }
26 }
27 for (i = m - 1;i >= 1;i--) {
28 if (pre[i]) {
29 printf("%d\n",i);
30 break;
31 }
32 }
33 while (i != 1) {
34 out[top++] = idx[i];
35 i = pre[i];
36 }
37 sort(out,out + top);
38 for (i = 0;i < top;i++) {
39 printf("%d ",out[i]);
40 }
41 printf("\n");
42 return 0;
43 }
44