Code 備忘錄►DP

TIOJ::1067 . C.互質任務

http://tioj.infor.org/problems/1067
動態規劃加上一點數學概念。
最後還是看了提示才想到QAQ。

題目給你一個數列跟一個數字M。
數列中每個數字都在區間[0,9]裡，把數列裡的某個子序列拿出來可以組成一個十進位數字。
而題目要求我們找出一個最長的子序列，條件是組成的十進位數字必須要和M互質。

一開始可能會想到爆搜，亂取子序列弄成大數然後跟M做GCD。
這很顯然是個時間空間還有編成複雜度都非常高的作法，可是這題的AC人數反映出他不是這種垃圾題XD。

於是就可以開始思考作法了，第1個直覺就是DP，可是要先處理檢查互質的問題。
觀察一下可以發現，如果用輾轉相除法找公因數的話，可以先取餘數，於是我們可以先紀錄要檢查的數字的餘數，再和M做GCD。
然後狀態就出來了（明明很直觀我卻還偷看了解答才發現QAQ），也就是對於每個狀態DP[i][j]，紀錄0～i之間，除以M的餘數是j的最長子序列長度是多少，這樣我們可以透過餘數的運算輕鬆推倒出所有餘數的狀態的最長子序列長度，而最後的答案就是和M互質的那些j的答案取MAX。

要注意的問題有，除了j==0的狀況外，如果DP[i][j]的值等於0，代表可以變出餘數j的子序列並不存在，這種情況不可以轉移，不然會有不存在的答案出現。
另外就是陣列初始化的時候注意一下，因為這裡的DP只會用到前一行的狀態，所以可以滾動，每次滾動要先把上一次的狀態複製到現在的狀態裡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 1001,M = 10001;
int DP[2][M];
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,a,p;
    while(cin>>n>>m, n||m){
        memset(DP[0],0,m*4);
        memset(DP[1],0,m*4);
        F(n){
            cin>>a;
            p = i&1;
            Fi(j,m)if(!j||DP[p][j]){
                int &next = DP[!p][(j*10+a)%m];
                next = max(next, DP[p][j]+1);
            }
            memcpy(DP[p], DP[!p], m*4);
            // Fi(j,m)DP[p][j] = DP[!p][j];
            // Fi(j,m)cout<<DP[!p][j]<<' ';cout<<endl;
        }
        int ans = 0;
        F(m)if(__gcd(i,m)==1){
            // cout<<"JIZZ"<<endl;
            ans = max(ans, DP[n&1][i]);
        }
        cout<<ans<<'\n';
    }
}