《貪婪的動态規劃》

• 狀态的定義與轉移
• 貪心思想對動态規劃的優化

确定狀态

• 青蛙的煩惱 LSGDOJ 1852

題目描述

池塘中有n片荷葉恰好圍成了一個凸多邊形，有一隻小青蛙恰好站在1号荷葉上，小青蛙想通過最短的路程周遊所有的荷葉（經過一個荷葉一次且僅一次），小青蛙可以從一片荷葉上跳到另外任意一片荷葉上。

輸入

 第一行為整數n，荷葉的數量。 接下來n行，每行兩個實數，為n個多邊形的頂點坐标，按照順時針方向給出。保證不會爆double。 

輸出

周遊所有荷葉最短路程，請保留3位小數。 

樣例輸入

4 50.0 1.0 5.0 1.0 0.0 0.0 45.0 0.0

樣例輸出

50.211

提示

對于所有資料,0<n<=720    分析：

LSGDOJ 1852 青蛙的煩惱

狀态定義：

• ​從 i 點出發，順時針or 逆時針 走 j 步的最少距離（最優解），但是狀态轉移很麻煩，首先第一維是 j，第二維是起點，但是狀态轉移很難表示，從 i 點出發，還走 j-1 步？不一定，可以從從其他點，而不是相鄰的點轉移而來。是以走了，或者要走的節點，沒有表示到dp狀态中，轉移方程很難寫出來，加一維枚舉從哪裡來，時間不允許。步數也難确定了，于是考慮别的狀态定義。

  

• 考慮順序，​ 從 I 結點，通路 剩下的 i+1,然後走i+2,...,i+j-1的最優解。從 i+j-1 結點開始，通路 剩下的i, i + 1,i+2,...,i+j-2 的最優解。

  

有了通路的順序定義，狀态轉移就得到是：

貪心思想展現于凸多邊形走法，不存在交叉路線。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000;

struct  Node {
    double x,y;
}nodes[maxn];

double dist[maxn][maxn];
double dp[maxn][maxn][2];


int main(int argc, char const *argv[]) {

    freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%lf%lf",&nodes[i].x,&nodes[i].y);
    }


    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dist[i][j] = sqrt((nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x)+(nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y));


    for (int i = 1; i <= n; ++i)
        dp[i][1][0] = dp[i][1][1] = 0;

    for(int j=2;j<=n;j++) {
        for(int i=1;i<=n;i++) {
            dp[i][j][0] = min(dist[i][i+1]+dp[i+1][j-1][0],dist[i][i+j-1]+dp[i+1][j-1][1]);
            dp[i][j][1] = min(dist[i][i+j-1]+dp[i][j-1][0],dist[i+j-1][i+j-2]+dp[i][j-1][1]);
        }
    }

    printf("%lf\n",min(dp[1][n][0],dp[1][n][1]));

    return 0;
}      

View Code

轉載于:https://www.cnblogs.com/TreeDream/p/7323746.html