**第四、五周 acm刷題總結 線性DP**

                                                學習DP是前所未有的挑戰，
           今天對動態規劃有了新的認識，之前認為它是一個采集更優解的程序，是太片面了，
   今天遇到一個題，發現更優解不是動規采集的，動規本質上只是把每一個子狀態存下來而
   已，以前說起動態規劃就想到背包，并且很多都能把那一套理論套上，現在發現更加通用
   的理解方式，應該是遞推，就找到子狀態和遞推方式就好了，
   			今天遇到的題是雇傭工人的問題，告訴工程持續的月數，告訴每個月雇傭、薪資、和
   	解雇每一個工人所需要的錢，再輸入每一個月需要的人數，求這么多月總共的最低成本，
   	首先確定子狀態，找子狀態我是套一句模板：想知道當前（），需要知道（），括號里面的東西
   	找起來有較大難度，那么想知道當前月份用某一數量工人的累積最小成本，需要知道上一個月份
   	所有可能數量的工人下那些累積的最小成本，然后分別根據那些狀態和當前狀態的差異，算出通過
   	那些狀態轉移到當前狀態所得的最終累積成本，再求最小值，這樣就得到了當前月份每一種工人數可能
   	所需要的最小成本，這些最小成本可以用于遞推下一個月份的每一種工人數可能所需要的最小成本，
   	代碼如下：

#include <iostream>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);

    int m;
        while (cin >> m, m) {
        int hire, salary, fire;
                cin >> hire >> salary >> fire;

                int ma = 0, require[500];
                for (int i = 1; i <= m; i++) {
            cin >> require[i];
                        if (require[i] > ma) ma = require[i];
                }
                int dp[2][500] = { 0 }, temp;

                for (int i = require[1]; i <= ma; i++) {
                                dp[1][i] = (hire + salary) * i;

                }
                for (int i = 2; i <= m; i++) {
                for (int j = require[i]; j <= ma; j++) {
                                int mi = INF;
                for (int k = require[i - 1]; k <= ma; k++) {
                if (k <= j) temp = hire * (j - k) + salary * j + dp[(i - 1) & 1][k];
                                        else temp = (k - j) * fire + j * salary + dp[(i - 1) & 1][k];
                                mi = min(temp, mi);
                }
                                dp[i & 1][j] = mi;
                        }
                }
                int MI = INF;
                for (int i = require[m]; i <= ma; i++) MI = min(dp[m & 1][i], MI);

                cout << MI << endl;
        }

        return 0;
}

   又是一個問題卡了一夜真是氣死我了，還好，解決了，值得一寫，
   之前一直認為動態規劃的空間優化是只要只和上一行或者前幾行有關，
   就可以通過取模使用滾動陣列，
   滾動陣列維護著最近這幾行的所有子狀態，里面的狀態可以隨意挑選使用，
   今天才發現滾動陣列無法維護當前行，
   其實我本來也沒認為滾動陣列能夠維護當前行呀，竟然錯得如此自然，
   因為不難想到，當對i下標取模的時候，下標已經變了，怎么可以把他索引到的值當成i索引到的值呢，
   它和i - 1不一樣，當對i - 1取模的時候，由于上一次遍歷到i - 1 的時候資料原本就存在i-1取模之后做下標索引到的位置，
   所以i- 1是被取模之后的陣列維護的，而i并沒有得到這種維護，
  今天做了道題，題意是說輸入正整數序列的最大元素n和序列長度k，
  要求序列中每個數都能被他左鄰整除，每個元素均可取1到n任何數，
  輸出滿足要求的序列個數，
  把他按照序列長度遞增順序分成k個階段，
  每個階段列舉末尾和倒數第二位的不同組合，代碼如下：

#include <iostream>
using namespace std;

const int mod = 1e9 + 7;
int dp[2005][2005];
int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);

        int n, k;
        cin >> n >> k;

        for (int i = 1; i <= n; i++)
                dp[1][i] = 1;

        for (int i = 2; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
                        for (int k = 1; k * j <= n; k++) {
                dp[i][j * k] = (dp[i - 1][k] + dp[i][j * k]) % mod;

                        }
                }

        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
        sum = (sum + dp[k][i]) % mod;
        }
        cout << sum << endl;
        return 0;
}

此處空間優化非必要，但是方法很重要，當需要用到當前行的時候，就需要進行細節上的處理，因為當前行取模并沒有得到維護，而是回傳開始的位置了，加一條if陳述句防止他跑回去，

#include <iostream>
using namespace std;

const int mod = 1e9 + 7;
int dp[2][2005];
int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);

        int n, k;
        cin >> n >> k;

        for (int i = 1; i <= n; i++)
                dp[1][i] = 1;

        for (int i = 2; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
                        for (int k = 1; k * j <= n; k++) {
                                if (j == 1) dp[i & 1][k] = dp[(i - 1) & 1][k];
                                else dp[i & 1][j * k] = (dp[(i - 1) & 1][k] + dp[i & 1][j * k]) % mod;
                        }
                }

        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
        sum = (sum + dp[k & 1][i]) % mod;
        }
        cout << sum << endl;
        return 0;
}