Ural 1029 Ministry 題解

来源:https://www.cnblogs.com/bitstd/archive/2019/08/06/11312487.html
-Advertisement-
Play Games

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:

  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))
#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**************************************************************/

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • RocketMQ中Broker的刷盤源碼分析
    上一篇博客的最後簡單提了下CommitLog的刷盤 【RocketMQ中Broker的消息存儲源碼分析】 （這篇博客和上一篇有很大的聯繫） Broker的CommitLog刷盤會啟動一個線程，不停地將緩衝區的內容寫入磁碟（CommitLog文件）中，主要分為非同步刷盤和同步刷盤 非同步刷盤又可以分為兩種 ...
  • Python連載29-log的使用需求實現舉例
    一、Format類 1.直接實例化 2.可以繼承Format添加特殊字元 3.三個參數 （1）fmt：指定消息格式化字元串，如果不指定該參數則預設使用message的原始值 （2）datemt：指定日期格式字元串，如果不指定該參數，則預設使用“%Y-%m-%d %H:%M:%S" （3）style: ...
  • 一個微信號同時支持多個環境網頁授權
    項目進行微信開發， 認證了一個微信服務號專門用於內部測試，但是內部可能存在多套不同環境(開發dev、測試sit、預發佈uat)等，由於微信限制一個服務號只能配置一個網頁授權功能變數名稱， 又不可能給每個環境單獨配一個服務號，這樣不僅需要成本而且很浪費資源， 所以重點需要解決下麵這個問題： 1、可以自動區分環 ...
  • PHP基礎之函數
    函數概念： 函數是用來完成某種特定任務的可重用代碼塊; 函數可以使程式更具模塊化,擁有良好的結構; 函數定義後在程式中可以重覆調用; 函數分為內置函數和自定義函數 考點： 變數的作用域和靜態變數 延伸1，函數的參數及參數的引用傳遞。 延伸2，函數的返回值及引用返回。 延伸3，外部文件的導入。 延伸4 ...
  • Qt實現表格樹控制項-自繪樹節點虛線
    [TOC] 原文鏈接： "Qt實現表格樹控制項 自繪樹節點虛線" 一、開心一刻 一程式員第一次上女朋友家她媽板著臉問 ：你想娶我女兒，有多少存款？ 程式員低了下頭：五百！ 她媽更鄙視了：才五百塊，買個廁所都不夠！ 程式員忙說：不是人民幣！ 她媽：就算是美元，還是不夠買廁所！ 程式員：其實是比特幣！ 她 ...
  • 後端基於方法的許可權控制--Spirng-Security
    後端基於方法的許可權控制 Spirng Security 預設情況下, Spring Security 並不啟用方法級的安全管控. 啟用方法級的管控後, 可以針對不同的方法通過註解設置不同的訪問條件；Spring Security 支持三種方法級註解, 分別是 JSR 205/Secured 註解/p ...
  • Java描述設計模式(06)：建造者模式
    一、生活場景 基於建造者模式，描述軟體開發的流程。 1、代碼實現 2、代碼結構圖 二、建造者模式 1、基礎概念 建造模式是對象的創建模式。建造模式可以將一個產品的內部屬性描述與產品的生產過程分割，從而可以使一個建造過程生成具有不同的內部表象的產品對象。也就是使用一個中介對象封裝一系列的對象交互，使其 ...
  • 小白之旅2
    一. 數據類型轉換 1.1 自動類型轉換 又叫：隱式類型轉換 概念：數據範圍小的類型能自動轉換成數據範圍大的類型 byte short int long float double 1.2 強制類型轉換 概念：將數據範圍大的類型使用指定格式轉換成數據範圍小的類型 格式：範圍小的數據類型 變數名 = ( ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類