題目描述

某地臨時居民想獲得長期居住權就必須申請拿到紅牌。獲得紅牌的過程是相當復雜，一共包括?N?個步驟。每一步驟都由政府的某個工作人員負責檢查你所提交的材料是否符合條件。為了加快進程，每一步政府都派了?M?個工作人員來檢查材料。不幸的是，并不是每一個工作人員效率都很高。盡管如此，為了體現“公開政府”的政策，政府部門把每一個工作人員的處理一個申請所花天數都對外界公開。

為了防止所有申請人都到效率高的工作人員去申請。這?M×N?個工作人員被分成?M?個小組。每一組在每一步都有一個工作人員。申請人可以選擇任意一個小組也可以更換小組。但是更換小組是很嚴格的，一定要相鄰兩個步驟之間來更換，而不能在某一步驟已經開始但還沒結束的時候提出更換，并且也只能從原來的小組?I?更換到小組?I+1，當然從小組?M?可以更換到小組 1。對更換小組的次數沒有限制。

例如：下面是 3 個小組，每個小組 4 個步驟工作天數：

• 小組 1: 2, 6, 1, 8;
• 小組 2: 3, 6, 2, 6;
• 小組 3: 4, 2, 3, 6。

例子中，可以選擇小組 1 來完成整個過程一共花了?2+6+1+8=17?天，也可以從小組 2 開始第一步，然后第二步更換到小組 3，第三步到小組 1，第四步再到小組 2，這樣一共花了?3+2+1+6=12?天。你可以發現沒有比這樣效率更高的選擇。

你的任務是求出完成申請所花最少天數。

輸入格式

第一行是兩個正整數?N?和?M，表示步數和小組數。

接下來有?M?行，每行有?N?個非負整數，第?i+1（1≤i≤M）行的第?j?個數表示小組?i?完成第?j?步所花的天數，天數都不超過 1000000。

輸出格式

一個正整數，為完成所有步所需最少天數。

輸入輸出樣例

輸入 #1

4 3
2 6 1 8
3 6 2 6
4 2 3 6

輸出 #1

12

說明/提示

對于 100% 的數據，1≤N,M≤2000。

思路：

狀態方程：1選擇當前行 2選擇鄰接行

3.到達m層需要特判回到1層。

代碼如下：

爆搜：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n,m;
ll arr[2000][2000];
ll dfs(ll x,ll y)
{ll sum1 = 1e9,sum2 = 1e9;if(y > n)//y是步數限制 return 0;sum1 = dfs(x,y+1)+arr[x][y];int xx = x + 1;if(xx > m)xx = xx - m;sum2 = dfs(xx,y+1)+arr[xx][y]; return min(sum1,sum2);
}
int main() 
{ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;//n是步數，m是小組數 for(ll i = 1 ; i <= m ; i++){for(ll j = 1 ; j <= n ; j++){cin >> arr[i][j];}}ll ans = 1e9;for(ll i = 1 ; i <= m ; i++){ans = min(ans,dfs(i,1));}cout << ans;return 0;
}

記憶化搜索：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n,m;
ll arr[2000][2000];
ll mem[2005][2005];
ll dfs(ll x,ll y)
{if(mem[x][y])return mem[x][y];ll sum1 = 1e9,sum2 = 1e9;if(y > n)//y是步數限制 return 0;sum1 = dfs(x,y+1)+arr[x][y];int xx = x + 1;if(xx > m)xx = xx - m;sum2 = dfs(xx,y+1)+arr[xx][y]; mem[x][y] = min(sum1,sum2);return mem[x][y];
}
int main() 
{ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;//n是步數，m是小組數 for(ll i = 1 ; i <= m ; i++){for(ll j = 1 ; j <= n ; j++){cin >> arr[i][j];}}ll ans = 1e9;for(ll i = 1 ; i <= m ; i++){ans = min(ans,dfs(i,1));}cout << ans;return 0;
}

dp: