P1359租用游艇（dp+dfs)

好久真的是好久没有做dp的问题了（ＱＷＱ）（我有学过这玩意？？？）

诶，人生呐！

今天来一个动归～

顺便可以回顾一下dfs.

这个题我觉得审题也非常重要

小可爱dp:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int f[201],n,i,j,x; //f[x]表示从1到x的距离
 4 int main()
 5 {
 6     scanf("%d",&n);
 7     for (i=1;i<=n;i++)
 8         for (j=i+1;j<=n;j++)
 9         {
10             scanf("%d",&x);
11             if (f[j]==0||f[j]>f[i]+x) //如果j还没有到过或者到j的距离比原来短
12                 f[j]=f[i]+x; //替换
13         }
14     printf("%d
",f[n]); //输出到n的距离
15 }

 1 //好久没有写dfs啦
 2 // Created by snnnow on 2020/7/19.
 3 //
 4 
 5 #include<iostream>
 6 #include<stdio.h>
 7 #include<stdlib.h>
 8 #include<time.h>
 9 #include <queue>
10 using namespace std;
11 int n,m[201][201],ans=9999999;
12 void dfs(int ,int);//层数，方法数
13 int main(){
14     scanf("%d",&n);
15     for (int i = 1; i <= n; ++i) {
16         for (int j = i+1; j <= n ; ++j) {
17             scanf("%d",&m[i][j]);
18         }
19 
20     }
21     dfs(1,0);
22     printf("%d",ans);
23 }
24 void dfs(int c,int ways){//你用的是dfs!!!找递归边界！！！
25     if(ways>ans)
26         return ;//剪枝，剪掉多余的部分
27     if(c==n) {
28         ans = ways;
29         return;
30     }
31     for (int i = 1+c; i <=n  ; ++i) {//枚举下游各个点
32         dfs(i,ways+m[c][i]);
33 
34     }
35 
36 }