CCYL Membership Activist

题解 P1796 【汤姆斯的天堂梦】

2020-09-16 21:46:42


(本蒟蒻第一次写题解,写的不好请见谅)
这是一道非常基础的动归题,看题解区有dalao说可以从上到下写,但是我不会啊。(叹气)

关于动态规划(DP)
动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
资料来源:百度百科
说人话,其实就像是你在做数学计算题的时候利用上一道题的结果推出下一道题的答案。

虽然这题十分简单但是还是单贴一下转移方程吧:
$ans(i,j)=min(ans(i,j),ans(i-1,root(i,j))+cost(i,j,root(i,j))$
好了 代码附上。

//lg-1796
#include<iostream>
using namespace std;
int k[105]/*同题目中Ki*/,r[105][105][105]/*联通第i层第j个星球的第k个i-1层星球编号*/,c[105][105][105]/*c[i][j][k]为r[i][j][k]对应的花费*/,ans[105][105],n,ri,ci,f_ans=214783647;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;//输入层数
    for(int i=1;i<=n;++i){
        cin>>k[i];//输入ki
        for(int j=1;j<=k[i];++j){
            while(true){
                cin>>ri;//输入联通的下层星球
                if(!ri) break;
                cin>>ci;//输入对应编号
                                //赋值
                ++r[i][j][0];
                r[i][j][r[i][j][0]]=ri;
                c[i][j][r[i][j][0]]=ci; 
            }
        }
    }
    for(int i=1;i<=n;++i){//从第1层开始规划
        for(int j=1;j<=k[i];++j){//规划第i层的第j个星球
            ans[i][j]=214783647;//初始化
            for(int no=1;no<=r[i][j][0];++no){//依次规划每条路径
                ans[i][j]=min(ans[i][j],ans[i-1][r[i][j][no]]+c[i][j][no]);//在当前解和(上一层联通城市最优解+上行花费)中选择最优者
            }
        }
    }
    for(int i=1;i<=k[n];++i) f_ans=min(f_ans,ans[n][i]);//选取第n层中的最优解
    cout<<f_ans;
    return 0;
}