设为首页 加入收藏

TOP

Ural 1029 Ministry 题解(一)
2019-08-14 00:08:45 】 浏览:40
Tags:Ural 1029 Ministry 题解

Ural 1029 Ministry 题解

题意

给定一个\(n\times m(1\le n \le10,1\le m \le500)\)的矩阵,矩阵中的每个值都是一个小于等于\(10^9\)的正整数。

现在从第\(1\)行的任意位置开始,在第\(n\)行的任意位置结束。每次有\(3\)种移动选择(不能移动到矩阵外)。

设当前位置为\((i,j)\)

  • 移动到\((i+1,j)\)

  • 移动到\((i,j-1)\)

  • 移动到\((i,j+1)\)

每条路径的价值是路径走过所有的位置上的值的和(小于等于\(10^9\))。

问在所有路径中,路径价值最小的,输出这条路径所有位置的列号。

题解

考虑记忆化搜索(DP也可以)。

对于每个点,记忆化搜索可以移动到它的\(3\)种位置,取最小值即可,顺便记录一下路径。

也可以无脑最短路。

Tips:

  1. WA\(1\)的同学不要着急,Test\(1\)并不是样例,仔细找找有没有错误。

  2. \((i,j)\)的答案为\(dp(i,j)\),矩阵中的值为\(a(i,j)\),状态转移方程如果是\(dp(i,j)=\min\{dp(i-1,j),dp(i,j-1),dp(i,j+1) \}+a(i,j)\)可能会WA\(1\),改为\(dp(i,j)=\min\{dp(i-1,j)+a(i,j),dp(i,j-1)+a(i,j),dp(i,j+1)+a(i,j) \}\)即可AC。目前并不知道原因(我太弱了),如果有知道的可以在评论区留言,谢谢!

程序

AC

// #pragma GCC optimize(2)
// #pragma G++ optimize(2)
// #pragma comment(linker,"/STACK:102400000,102400000")

// #include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <array>
#include <cfenv>
#include <cmath>
#include <ctime>
#include <deque>
#include <mutex>
#include <queue>
#include <ratio>
#include <regex>
#include <stack>
#include <tuple>
#include <atomic>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <chrono>
#include <cstdio>
#include <cwchar>
#include <future>
#include <limits>
#include <locale>
#include <memory>
#include <random>
#include <string>
#include <thread>
#include <vector>
#include <cassert>
#include <climits>
#include <clocale>
#include <complex>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <ctgmath>
#include <cwctype>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ccomplex>
#include <cstdbool>
#include <iostream>
#include <typeinfo>
#include <valarray>
#include <algorithm>
#include <cinttypes>
#include <cstdalign>
#include <stdexcept>
#include <typeindex>
#include <functional>
#include <forward_list>
#include <system_error>
#include <unordered_map>
#include <unordered_set>
#include <scoped_allocator>
#include <condition_variable>
// #include <conio.h>
// #include <windows.h>
using namespace std;

typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef float fl;
typedef double ld;
typedef long double LD;
typedef pair<int,int> pii;
#if (WIN32) || (WIN64) || (__WIN32) || (__WIN64) || (_WIN32) || (_WIN64) || (WINDOWS)
#define lld "%I64d"
#define llu "%I64u"
#else
#define lld "%lld"
#define llu "%llu"
#endif
#define ui(n) ((unsigned int)(n))
#define LL(n) ((long long)(n))
#define ull(n) ((unsigned long long)(n))
#define fl(n) ((float)(n))
#define ld(n) ((double)(n))
#define LD(n) ((long double)(n))
#define char(n) ((char)(n  
		
编程开发网
首页 上一页 1 2 3 4 5 下一页 尾页 1/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Qt实现表格树控件-自绘树节点虚线 下一篇洛谷P2763题解