洛谷 P1130 红牌 C语言

题目描述

某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂，一共包括 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: