Ural 1029 Ministry 题解
程序员文章站
2023-11-30 15:39:52
Ural 1029 Ministry 题解 [TOC] 题意 给定一个$n\times m(1\le n \le10,1\le m \le500)$的矩阵,矩阵中的每个值都是一个小于等于$10^9$的正整数。 现在从第$1$行的任意位置开始,在第$n$行的任意位置结束。每次有$3$种移动选择(不能移 ......
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:
wa\(1\)的同学不要着急,test\(1\)并不是样例,仔细找找有没有错误。
设\((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)) #define bool(n) ((bool)(n)) #define fixpoint(n) fixed<<setprecision(n) const int inf=1061109567; const int ninf=-1044266559; const ll linf=4557430888798830399; const ld eps=1e-15; #define mod (1000000007) #define pi (3.1415926535897932384626433832795028841971) /* #define mb_len_max 5 #define shrt_min (-32768) #define shrt_max 32767 #define ushrt_max 0xffffu #define int_min (-2147483647 - 1) #define int_max 2147483647 #define uint_max 0xffffffffu #define long_min (-2147483647l - 1) #define long_max 2147483647l #define ulong_max 0xfffffffful #define llong_max 9223372036854775807ll #define llong_min (-9223372036854775807ll - 1) #define ullong_max 0xffffffffffffffffull */ #define mp make_pair #define mt make_tuple #define all(a) (a).begin(),(a).end() #define pall(a) (a).rbegin(),(a).rend() #define log2(x) log(x)/log(2) #define log(x,y) log(x)/log(y) #define sz(a) ((int)(a).size()) #define rep(i,n) for(int i=0;i<((int)(n));i++) #define rep1(i,n) for(int i=1;i<=((int)(n));i++) #define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++) #define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++) #define repd(i,n) for(int i=((int)(n))-1;i>=0;i--) #define repd1(i,n) for(int i=((int)(n));i>=1;i--) #define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--) #define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--) #define for(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step))) #define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++) #define repv(i,v) for(auto i:v) #define repe(i,v) for(auto &i:v) #define ms(x,y) memset(x,y,sizeof(x)) #define mc(x) ms(x,0) #define minf(x) ms(x,63) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define sqr(x) ((x)*(x)) #define un(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define filein(x) freopen(x,"r",stdin) #define fileout(x) freopen(x,"w",stdout) #define fileio(x)\ freopen(x".in","r",stdin);\ freopen(x".out","w",stdout) #define filein2(filename,name) ifstream name(filename,ios::in) #define fileout2(filename,name) ofstream name(filename,ios::out) #define file(filename,name) fstream name(filename,ios::in|ios::out) #define pause system("pause") #define cls system("cls") #define fs first #define sc second #define pc(x) putchar(x) #define gc(x) x=getchar() #define endl pc('\n') #define sf scanf #define pf printf inline int read() { int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');} inline ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;} inline ll gcdll(ll a,ll b){return b?gcdll(b,a%b):a;} const int dx[]={0,1,0,-1,1,-1,-1,1}; const int dy[]={1,0,-1,0,-1,-1,1,1}; /************************************************************begin************************************************************/ const int maxn=110,maxm=510; int n,m,a[maxn][maxm],dp[maxn][maxm]; pair<int,int> pre[maxn][maxm]; inline int sol(int x,int y) { if(y<1||y>m) return dp[x][y]=inf; if(dp[x][y]!=-1) return dp[x][y]; else dp[x][y]=0; int res=sol(x-1,y)+a[x][y]; dp[x][y]=res; pre[x][y]={x-1,y}; res=sol(x,y-1)+a[x][y]; if(res<dp[x][y]) { dp[x][y]=res; pre[x][y]={x,y-1}; } res=sol(x,y+1)+a[x][y]; if(res<dp[x][y]) { dp[x][y]=res; pre[x][y]={x,y+1}; } return dp[x][y]; } inline void print(int x,int y) { if(x>1) print(pre[x][y].fs,pre[x][y].sc); cout<<y<<' '; } int main() { cin>>n>>m; rep1(i,n) rep1(j,m) cin>>a[i][j]; ms(dp,-1); rep1(j,m) dp[1][j]=a[1][j]; int ans=1; rep1(j,m) if(sol(n,j)<sol(n,ans)) ans=j; print(n,ans); return 0; } /*************************************************************end**************************************************************/
wa\(1\)程序
// #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)) #define bool(n) ((bool)(n)) #define fixpoint(n) fixed<<setprecision(n) const int inf=1061109567; const int ninf=-1044266559; const ll linf=4557430888798830399; const ld eps=1e-15; #define mod (1000000007) #define pi (3.1415926535897932384626433832795028841971) /* #define mb_len_max 5 #define shrt_min (-32768) #define shrt_max 32767 #define ushrt_max 0xffffu #define int_min (-2147483647 - 1) #define int_max 2147483647 #define uint_max 0xffffffffu #define long_min (-2147483647l - 1) #define long_max 2147483647l #define ulong_max 0xfffffffful #define llong_max 9223372036854775807ll #define llong_min (-9223372036854775807ll - 1) #define ullong_max 0xffffffffffffffffull */ #define mp make_pair #define mt make_tuple #define all(a) (a).begin(),(a).end() #define pall(a) (a).rbegin(),(a).rend() #define log2(x) log(x)/log(2) #define log(x,y) log(x)/log(y) #define sz(a) ((int)(a).size()) #define rep(i,n) for(int i=0;i<((int)(n));i++) #define rep1(i,n) for(int i=1;i<=((int)(n));i++) #define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++) #define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++) #define repd(i,n) for(int i=((int)(n))-1;i>=0;i--) #define repd1(i,n) for(int i=((int)(n));i>=1;i--) #define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--) #define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--) #define for(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step))) #define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++) #define repv(i,v) for(auto i:v) #define repe(i,v) for(auto &i:v) #define ms(x,y) memset(x,y,sizeof(x)) #define mc(x) ms(x,0) #define minf(x) ms(x,63) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define sqr(x) ((x)*(x)) #define un(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define filein(x) freopen(x,"r",stdin) #define fileout(x) freopen(x,"w",stdout) #define fileio(x)\ freopen(x".in","r",stdin);\ freopen(x".out","w",stdout) #define filein2(filename,name) ifstream name(filename,ios::in) #define fileout2(filename,name) ofstream name(filename,ios::out) #define file(filename,name) fstream name(filename,ios::in|ios::out) #define pause system("pause") #define cls system("cls") #define fs first #define sc second #define pc(x) putchar(x) #define gc(x) x=getchar() #define endl pc('\n') #define sf scanf #define pf printf inline int read() { int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');} inline ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;} inline ll gcdll(ll a,ll b){return b?gcdll(b,a%b):a;} const int dx[]={0,1,0,-1,1,-1,-1,1}; const int dy[]={1,0,-1,0,-1,-1,1,1}; /************************************************************begin************************************************************/ const int maxn=110,maxm=510; int n,m,a[maxn][maxm],dp[maxn][maxm]; pair<int,int> pre[maxn][maxm]; inline int sol(int x,int y) { if(y<1||y>m) return dp[x][y]=inf; if(dp[x][y]!=-1) return dp[x][y]; else dp[x][y]=0; int res=sol(x-1,y); dp[x][y]=res; pre[x][y]={x-1,y}; res=sol(x,y-1); if(res<dp[x][y]) { dp[x][y]=res; pre[x][y]={x,y-1}; } res=sol(x,y+1); if(res<dp[x][y]) { dp[x][y]=res; pre[x][y]={x,y+1}; } dp[x][y]+=a[x][y]; return dp[x][y]; } inline void print(int x,int y) { if(x>1) print(pre[x][y].fs,pre[x][y].sc); cout<<y<<' '; } int main() { cin>>n>>m; rep1(i,n) rep1(j,m) cin>>a[i][j]; ms(dp,-1); rep1(j,m) dp[1][j]=a[1][j]; int ans=1; rep1(j,m) if(sol(n,j)<sol(n,ans)) ans=j; print(n,ans); return 0; } /*************************************************************end**************************************************************/
上一篇: ps命令入门使用指南