每日小訓練

lsnu——dp題解

1.自然數拆分（計蒜客1248）

• 這道題和以前的一道題一摸一樣，但是這道題是求具體的拆分方案
• 這道題用深度搜索，一直去搜索直到找到滿足的情況，
  有什么種實作方法 但這份代碼我覺得最清楚明白

#include<iostream>
using namespace std;

const int N = 1e5;
int n;
int a[N];
void dfs(int sum , int len , int beginx)//sum 選的數的和 len 選了幾個數 beginx 選數的起點
{
    if(sum == n)
    {
        cout << n << "=" << a[0];
        for(int i = 1 ; i <len ; i++)
            cout << "+" << a[i];
        cout << endl;
        return ;
    }
    for(int i = 1 ; i <n ;i++)
    {
        if(sum + i <= n && i >= beginx)//  同一個數可以被多次選 ，又要滿足單增
        {
            a[len] = i;
            len ++;
            dfs(sum + i , len , i);
            len --;//回溯
        }
    }

}
int main()
{
    cin >> n;

    dfs(0 ,0 ,1);

    return 0;
}

2.走馬卒（計蒜客2118）

• 這是我在洛谷做的第一個題 現在終于做出來
• 看到的第一眼 可能會覺得這是一個非常模板的深度搜索題，但是只能過幾個資料，會超時，那么就用更少回圈的遞推 DP吧
• f[i , j]儲存的走到這個點有多少種走法 ，狀態的轉移是 f [i , j] = f[i -1 , j] + f[i , j-1] 也就是點（i ， j）由左邊的點走過來和上邊的點走過來，這個題的狀態轉移還有情況就是（i ，j）只能由左邊或者上邊走過來（受邊界影響or“馬”），那么f[i ， j]=f[i-1 ，j]<上面走過來>或者 f[i , j]=f[i , j-1] , 但是題中由于邊界和“馬”的存在還有一些特殊的情況需要討論
• 1 . （0 ，0~n）點也就是第一排的點 ， 這一排的點只能由左邊得來，同時如果在第一排中有“馬” ， 那么“馬”后面的點也就不可能走到

//dp[i][j初始為0，前一個點不能為“馬”點，如果前一個為“馬”那么這個點的走法為
//0，那么后續的點也就都為0了
if(mapx[i][j] != INF && mapx[i][j-1] != INF) dp[i][j] = dp[i][j-1];

• 2.（0~n ，0）點也就是第一列的點，和上一種情況類所

if(mapx[i][j] != INF && mapx[i-1][j] != INF) dp[i][j] = dp[i-1][j];

• 3中間的點分別討論 1.不能走到（上 左都是馬）2.只能由一種情況走到3.左邊和上邊都能走到

if(mapx[i][j] == INF) dp[i][j] = 0;
else if(mapx[i-1][j] == INF && mapx[i][j-1] == INF) dp[i][j] = 0;
else if(mapx[i-1][j] == INF) dp[i][j] = dp[i][j-1];
else if(mapx[i][j-1] == INF) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i-1][j] + dp[i][j-1];

給一個樣例的路線圖解

完整代碼

#include<iostream>

using namespace std;

const int N = 25;
const int INF = -1e5;
int bx , by , mx , my;
int mdirx[]={-2,-2,-1,-1,+1,+1,+2,+2};
int mdiry[]={-1,+1,-2,+2,-2,+2,-1,+1};
long long int mapx[N][N] , dp[N][N];//不開long long不能過

int main()
{
    cin >> bx >> by >> mx >> my;
    mapx[mx][my] = INF;
    for(int i = 0;i < 8 ;i++)
    {
        int x = mx + mdirx[i];
        int y = my + mdiry[i];
        if(x >= 0 && x <= bx && y>= 0 && y <= by)
            mapx[x][y] = INF;
    }//記錄馬的影響坐標
    for(int i = 0 ; i <= bx ; i++)
    {
        for(int j = 0 ; j <= by ; j++)
        {
            if(i == 0 && j == 0)dp[0][0] = 1;//初始化
            else if(i == 0)
            {
                if(mapx[i][j] != INF && mapx[i][j-1] != INF) dp[i][j] = dp[i][j-1];//if讓整個陣列的邊界都+1的話可以減少很多討論，但是這個沒有優化
//的最清晰吧 大家可以想想哦dp[0][x] = 0的話+ dp[0][x]也不會影響dp[0][x+1]
            }
            else if(j == 0)
            {
                if(mapx[i][j] != INF && mapx[i-1][j] != INF) dp[i][j] = dp[i-1][j];
            }
            else
            {
                if(mapx[i][j] == INF) dp[i][j] = 0;
                else if(mapx[i-1][j] == INF && mapx[i][j-1] == INF) dp[i][j] = 0;
                else if(mapx[i-1][j] == INF) dp[i][j] = dp[i][j-1];
                else if(mapx[i][j-1] == INF) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
           // cout << dp[i][j] << "(" << i <<"," << j << ")" << "  ";
        }
        //cout << endl;//有興趣的可以看看不同資料的圖解
    }

    cout << dp[bx][by] << endl;
    return 0;
}

我的寫法肯定很劣質 ， 還有更簡單的更巧妙的做法，下面的鏈接有各種解法
https://www.luogu.com.cn/problem/solution/P1002
3.大盜阿福（計蒜客1227）
這是一個DP問題，解題關鍵是找到滿足題目條件的狀態表示，
dp[i]儲存的是盜竊金額最大數，dp[i] : 前 i 個店中最優盜法 ， 對于每個店都有盜或者不盜的選擇（跟0 1背包問題很像）那么我們的狀態
dp[ i ] = max(dp[i-1]（不盜） , dp[i - 2] + a[i]（盜）);
注意邊界 i - 2的處理；

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int t;

int main()
{
    cin >> t;
    while(t--)
    {
        int n ;
        int a[N] , dp[N];
        cin >> n;
        for(int i = 1 ; i <= n ; i++)
            cin >> a[i];
        dp[1] = a[1];//i = 1直接選上，回圈從i = 2開始
        for(int i = 2 ; i <= n ; i++)
            dp[i] = max(dp[i-1] , dp[i-2] + a[i]);

        cout << dp[n] << endl;
    }

    return 0;
}

4.嚴酷的訓練（計蒜客1739）
這是一個模板的 0 1 背包問題，在規定的時間內選擇出最優的做題選擇
dp[ i ][j]儲存的是規定時間內在前 i 個問題且限制時間為j中選擇的最大得分 ， 對于每個問題我們都有選 or 不選
dp[i][j] = max(dp[i-1][j] , dp[i-1][j - 時間[i]] + 得分[i]) （還可以優化）

#include<iostream>

using namespace std;

const int N = 5500;
int k1,k2;
int m,n,limt;
int t[N];
int ch[N][2];
int dp[N];

int main()
{
    cin >> k1 >> k2;
    cin >> m >> n;
    for(int i = 1; i<=n; i++)
    {
        int tm;
        cin >> tm;
         t[i] = (k2 / k1) * tm;
    }//學生做第i題需要的時間
    for(int i =1; i <= m; i++)
        cin >> ch[i][0] >> ch[i][1];//記錄該題的編號和得分
    cin >> limt;
    for(int i = 1; i<= m ;i++)
        for(int j = limt; j >= t[ch[i][0]]; j--)//優化
            dp[j] = max(dp[j],dp[j - t[ch[i][0]]] + ch[i][1]);
//f[i][j] = f[i-1][j],if （j > t[ch[i][0]]）(for 從j=0開始)dp[i][j]
//=max(dp[i-1][j] , dp[i -1][j - t[ch[i][0]]] + ch[i][1]
    cout << dp[limt] << endl;

    return 0;
}