poj1695 dp思维不错

小灰灰 2022-05-14 15:10 103阅读 0赞

题意：给三辆车，将1~n这n个点依次跑完，也就是说要想到达i+1，必须先到达i，

每两个点之间都有花费，问最小的话费是什么。

思路：设dp\[i\]\[j\]\[k\]，为走的最远的车，次元的车，最近的车在位置i,j,k的时候的最小

花费。具体转移看代码，感觉非常巧妙。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int INF=0x3f3f3f3f;
    int dp[31][31][31];//分别为走的最远，次远，最近的车的位置
    int cost[31][31], n;
    
    int main(){
        int T;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
    
            for(int i=1; i<n; i++){
                for(int j=i+1; j<=n; j++){
                    scanf("%d", &cost[i][j]);
                }
            }
            memset(dp, 0x3f, sizeof dp);
            dp[1][1][1]=0;
    
            for(int i=1; i<=n; i++){//最远车的位置
                for(int j=1; j<=i; j++){//次远车的位置
                    for(int k=1; k<=j; k++){//最近车的位置
                        dp[i+1][j][k]=min(dp[i+1][j][k], dp[i][j][k]+cost[i][i+1]);
                        dp[i+1][i][k]=min(dp[i+1][i][k], dp[i][j][k]+cost[j][i+1]);
                        dp[i+1][i][j]=min(dp[i+1][i][j], dp[i][j][k]+cost[k][i+1]);
                    }
                }
            }
            int mn=INF;
            for(int j=1; j<=n; j++)
                for(int k=1; k<=j; k++)
                    mn=min(mn, dp[n][j][k]);
            printf("%d\n", mn);
    
    
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，103人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1661 暴力dp

题意略。思路：很有意思的一个题，我采用的是主动更新未知点的方式，也即刷表法来dp。我们可以把整个路径划分成横向移动和纵向移动，题目一开始就给出了Jimmy的高度，这

绝地灬酷狼/ 2023年08月17日 16:37/ 0 赞/ 67 阅读

相关 POJ 2955 区间dp

题意：求括号匹配的最大长度思路：简单区间dp，令dp\[i\]\[j\] 为区间（i,j）之间的最大匹配长度。这样dp\[i\]\[j\] = max( dp\[i

Love The Way You Lie/ 2022年08月18日 11:55/ 0 赞/ 153 阅读

相关 poj 2253（区间DP）

[原题][Link 1] 思路：求所有路径中最大跳跃距离的最小值，很诡异的是输出答案如果用G++，.3lf%格式会出错，c++可以过 include<cstdio

男娘i/ 2022年06月04日 03:05/ 0 赞/ 185 阅读

相关 poj1695 dp思维不错

题意：给三辆车，将1~n这n个点依次跑完，也就是说要想到达i+1，必须先到达i，每两个点之间都有花费，问最小的话费是什么。思路：设dp\[i\]\[j\]\[k\]，为

小灰灰/ 2022年05月14日 15:10/ 0 赞/ 104 阅读

相关 ZOJ-3543不错的dp

-------------------- title: ZOJ-3543不错的dp date: 2018-11-01 16:40:58 tags: dp

墨蓝/ 2022年04月22日 02:26/ 0 赞/ 131 阅读

相关 poj3666（DP+离散化）

题目链接：http://poj.org/problem?id=3666 思路：看了讨论区说本题的数据比较弱，只需要考虑不减序列即可，比较懒，所以我也只写了这一部分的代码，

约定不等于承诺〃/ 2021年12月21日 01:05/ 0 赞/ 223 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 278 阅读

相关【dp】POJ-1050

从里面任意截取一个矩阵,使得矩阵所包含的数字的和最大. 首先考察该题的简化版：已知一列数，求任意连续若干个数和的最大值。因为是连续若干个自然数的和，那前面的某个数字取

淩亂°似流年/ 2021年12月05日 13:09/ 0 赞/ 223 阅读

相关 poj1037（计数dp）

题意：给定n个数字，规定一种 cute 排序：序列中的数字大小为严格的波浪形，即 a\[0\] > a\[1\] < a\[2\] > a\[3\] < .... 或者 a\

àì夳堔傛蜴生んèń/ 2021年11月29日 14:42/ 0 赞/ 277 阅读

相关 C. Two Arrays (dp、思维)

[题目][Link 1] a\[i\]\[j\] 表示前i个数字中第i个数字为j的所有情况的非递减序列的数目 b\[i\]\[j\] 表示前i个数字中第i个数字为j

浅浅的花香味﹌/ 2021年07月16日 19:19/ 0 赞/ 404 阅读