给出一张有向图和从第i条边到n的条边的所有花费，求最少的租金
思路：
dp想不明白，虽然我是在训练dp…
图论的话，单源最短路可以用迪杰斯特拉叭
也不需要堆优化，朴素的迪杰斯特拉也能过
#include<bits/stdc++.h> using namespace std; int a[202][202]; int g[202]; int n; bool st[202]; void dijkstra() { g[1]=0; for(int i=1;i<=n;i++) { int t=-1; for(int j=1;j<=n;j++) { if(st[j]==0&&(t==-1||g[t]>g[j])) { t=j; } } st[t]=1; for(int j=1;j<=n;j++) { g[j]=min(g[j],a[t][j]+g[t]); } } } int main() { int i,j; cin>>n; memset(a,0x3f,sizeof a); memset(g,0x3f,sizeof g); memset(st,0,sizeof st); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { cin>>a[i][j]; } } dijkstra(); cout<<g[n]<<endl; return 0; }
但其实这题其实不需要用到图，可以用更直观的普通DP方法。
p[i]表示到i站时的最少租金，m[j][i]表示j到i站的租金。
那么很简单的就能发现：
i = 2 to n
j = 1 to i
p [ i ] = min( p [ i ] , p [ j ] + m [ j ][ i ] )
#include<bits/stdc++.h> using namespace std; int dp[202],a[202][202]; int main() { int n,i,j,t; cin>>n; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { cin>>a[i][j]; } dp[i]=0x3f; } dp[1]=0; for(i=2;i<=n;i++) { for(j=1;j<i;j++) dp[i]=min(dp[i],dp[j]+a[j][i]); } cout<<dp[n]<<endl; return 0; }
