蒟蒻の小窝（关于动态规划再总结）

我们以城市交通网和挖地雷来说明两个常见DP！！！
我谔谔，你们肯定觉得很简单的。。。
`
样例输入：
10
0 2 5 1 0 0 0 0 0 0
0 0 0 0 12 14 0 0 0 0
0 0 0 0 6 10 4 0 0 0
0 0 0 0 13 12 11 0 0 0
0 0 0 0 0 0 0 3 9 0
0 0 0 0 0 0 0 6 5 0
0 0 0 0 0 0 0 0 10 0
0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
【样例输出】short.out

minlong=19

1 3 5 8 10
【算法分析】逆推法

设f[i]表示点i到v10的最短路径长度，则 f[10]=0
f[i]=min{ a[i][x]+f[x] 当a[i][x]>0 ,i<x<=n时}

#include<iostream>
　#include<cstring>
　#include<cstdio>
　using namespace std;
　int main()
{
　   long n,i,j,x,f[100],c[100],a[100][100]; 
　   memset(a,0,sizeof(a));
　   memset(c,0,sizeof(c));
　   cin>>n;
　   for (i=1;i<=n;i++)                         //输入各个城市之间距离
　     for (j=1;j<=n;j++)
　       cin>>a[i][j];
　   for (i=1;i<=n;i++)
　     f[i]=1000000;                            //初始化，默认每一个城市到达终点都是1000000
　   f[n]=0;
　   for (i=n-1;i>=1;i--)                       //从终点往前逆推，计算最短路径
　    for (x=i+1;x<=n;x++)                      //若f[x]=1000000表示城市x到终点城市不通
　     if ((a[i][x]>0)&&(f[x]!=1000000)&&(f[i]>a[i][x]+f[x])) 
　      {                                       //a[i][x]>0表示城市i和城市x通路
　        f[i]=a[i][x]+f[x];                    //城市i到终点最短路径的值
　        c[i]=x;
　      }
　    cout<<"minlong="<<f[1]<<endl;             //输出最短路径的值
　    x=1;
   while (x!=0)                              //输出路过的各个城市
　    {
　      cout<<x<<' ';
        x=c[x];
　    } 
　    cout<<endl; 
}


```c
在这里插入代码片

我谔谔
继续看挖地雷这题
【问题描述】
　　在一个地图上有N个地窖（N<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。
　　读完题干你要明白这种题的最大值不是在f[1]取到，因为他没有设置起点值！！！
　　所以必须最后对目标数组进行遍历，求最大值，其他步骤和上题一样！！！
　　【输入格式】
N //地窖的个数
W1，W2，……WN //每个地窖中的地雷数
X1，Y1 //表示从X1可到Y1
X2，Y2
……
0，0 //表示输入结束
【输出格式】
K1-K2-…-Kv //挖地雷的顺序
MAX //最多挖出的地雷数
【输入样例】Mine.in
6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0
【输出样例】Mine.out
3-4-5-6
34
【算法分析】
　　本题是一个经典的动态规划问题。很明显，题目规定所有路径都是单向的，所以满足无后效性原则和最优化原理。设W[i]为第i个地窖所藏有的地雷数，A[i][j]表示第i个地窖与第j个地窖之间是否有通路，F[i]为从第i个地窖开始最多可以挖出的地雷数，则有如下递归式：
　　F[i]=max{ W[i]+ F[j]} (i<j<=n , A[i][j]=true)
　　边界：F[n]=W[n]
　　于是就可以通过递推的方法，从后F(n)往前逐个找出所有的F[i]，再从中找一个最大的即为问题2的解。对于具体所走的路径（问题1），可以通过一个向后的链接来实现。

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
   long f[201]={0},w[201],c[201]={0};
   bool a[201][201]={0};
   long i,j,n,x,y,l,k,maxx;
   memset(f,0,sizeof(f));
   memset(c,0,sizeof(c));
   memset(a,false,sizeof(a));
   cin>>n;
   for (i=1;i<=n;i++)
     cin>>w[i];                                //输入每个地窖中的地雷数
   do
    {
      cin>>x>>y;                               //表示从X可到Y
      if ((x!=0)&&(y!=0)) a[x][y]=true;
    }while ((x!=0)||(y!=0));
    f[n]=w[n];                                 //从后F[n]往前逐个找出所有的F[i]
    for (i=n-1;i>=1;i--)
     {
      l=0;k=0;
      for (j=i+1;j<=n;j++)
       if ((a[i][j])&&(f[j]>l))
         { l=f[j]; k=j; }
      f[i]=l+w[i];                             //保存从第i个地窖起能挖到最大地雷数
      c[i]=k;                                  //k地窖是i地窖最优路径
     }
     k=1;
     for (j=2;j<=n;j++)                        //计算最多挖出的地雷数
      if (f[j]>f[k]) k=j;
     maxx=f[k];
     cout<<k;
     k=c[k];
     while (k!=0)                              //输出挖地雷的顺序
      {
        cout<<"-"<<k;
        k=c[k];
      } 
     cout<<endl;
     cout<<maxx<<endl;                          //输出最多挖出的地雷数
}

```c
在这里插入代码片

几句蒟蒻的感悟：DP的难点在于状态转移方程，目前就此点延伸出来的背包问题，期望DP，状压DP，树状DP。。。都是蒟蒻不会或者不熟的，从最简单的学，一定要领悟思想啊啊啊啊！！！状态转移方程！！！