pku 1695 Magazine Delivery

心已赠人 2022-08-14 00:42 14阅读 0赞

\#include <iostream> using namespace std; int dis\[32\]\[32\]; int dp\[32\]\[32\]\[32\]; \#define MAX 0x01010101 //三维动态规划: 本题采用递推的方式 //设我们假设某一时刻三辆车分别在i,j,k三个位置. 不妨采取递推的方式继续下去: //到第k点的可能状态有: // dp\[i\]\[j\]\[k\]+dis\[i\]\[k+1\](dp\[j\]\[k\]\[k+1\], dp\[k\]\[j\]\[k+1\]) // dp\[i\]\[j\]\[k\]+dis\[j\]\[k+1\](dp\[i\]\[k\]\[k+1\], dp\[k\]\[i\]\[k+1\]) // dp\[i\]\[j\]\[k\]+dis\[k\]\[k+1\](dp\[i\]\[j\]\[k+1\], dp\[j\]\[i\]\[k+1\]) //其中dp\[i\]\[j\]\[k\]表示三辆车分别在i,j,k位置时的最小时间(也就是到k). int main() \{ int N; scanf("%d", &N); while(N--) \{ //input int n; scanf("%d", &n); for(int i = 1; i <= n-1; ++i) for(int j = i+1; j <= n; ++j) \{ scanf("%d", &dis\[i\]\[j\]); dis\[j\]\[i\] = dis\[i\]\[j\]; \} //dp memset(dp, 0x01, sizeof(dp)); dp\[1\]\[1\]\[1\] = 0; for(int k = 1; k <= n-1; ++k) for(int i = 1; i <= k; ++i) for(int j = 1; j <= k; ++j) if(dp\[i\]\[j\]\[k\] != MAX) \{ if(dp\[j\]\[k\]\[k+1\] > dp\[i\]\[j\]\[k\]+dis\[i\]\[k+1\]) \{ dp\[j\]\[k\]\[k+1\] = dp\[i\]\[j\]\[k\]+dis\[i\]\[k+1\]; dp\[k\]\[j\]\[k+1\] = dp\[i\]\[j\]\[k\]+dis\[i\]\[k+1\]; \} if(dp\[i\]\[k\]\[k+1\] > dp\[i\]\[j\]\[k\]+dis\[j\]\[k+1\]) \{ dp\[i\]\[k\]\[k+1\] = dp\[i\]\[j\]\[k\]+dis\[j\]\[k+1\]; dp\[k\]\[i\]\[k+1\] = dp\[i\]\[j\]\[k\]+dis\[j\]\[k+1\]; \} if(dp\[i\]\[j\]\[k+1\] > dp\[i\]\[j\]\[k\]+dis\[k\]\[k+1\]) \{ dp\[i\]\[j\]\[k+1\] = dp\[i\]\[j\]\[k\]+dis\[k\]\[k+1\]; dp\[j\]\[i\]\[k+1\] = dp\[i\]\[j\]\[k\]+dis\[k\]\[k+1\]; \} \} // find min int min = MAX; for(int i = 1; i <= n-1; ++i) for(int j = 1; j <= n-1; ++j) if(dp\[i\]\[j\]\[n\] < min) min = dp\[i\]\[j\]\[n\]; printf("%d/n", min); \} return 0; \}

发表评论取消回复

表情：

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

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

相关阅读

相关 hdu1695（容斥原理）

求（1，b）区间和（1，d）区间里面gcd(x, y) = k的数的对数（1<=x<=b , 1<= y <= d）。 b和d分别除以k之后的区间里面，只需要求gcd(x,

一时失言乱红尘/ 2024年02月17日 23:41/ 0 赞/ 60 阅读

相关 pku 3176 水

\include <iostream> \include <cstdio> \include <cstring> using namespace std; int map\[3

我不是女神ヾ/ 2022年08月14日 04:46/ 0 赞/ 168 阅读

相关 pku 1695 Magazine Delivery

\include <iostream> using namespace std; int dis\[32\]\[32\]; int dp\[32\]\[32\]\[32\];

心已赠人/ 2022年08月14日 00:42/ 0 赞/ 15 阅读

相关 pku 3356 AGTC

\include <iostream> \include <string> using namespace std; int v\[1001\]\[1001\]; int ma

客官°小女子只卖身不卖艺/ 2022年08月13日 17:40/ 0 赞/ 16 阅读

相关 pku 1088 滑雪

\include <iostream> using namespace std; int map\[100\]\[100\]; int v\[100\]\[100\]; int

╰半夏微凉°/ 2022年08月13日 12:46/ 0 赞/ 193 阅读

相关 pku 1101 bfs

/\ //很很很经典的bfs, 这也是我第一次正式用bfs来刷题, 感受颇深: //one.cpp是用bfs来解决从一个点到另一个点的最短路程长度的方法(写的有点冗杂) 注意的

向右看齐/ 2022年08月13日 12:37/ 0 赞/ 184 阅读

相关 HDU 1695 GCD （容斥原理）

[HDU 1695][] 题意：求有多少对(x,y), (1<=x<=b,1<=y<=d), 满足gcd(x,y)=k。题解：注意到gcd(x,y)=k,说明x,y

男娘i/ 2022年07月12日 09:55/ 0 赞/ 242 阅读

相关 pku 3176

\include<stdio.h> int str\[351\]\[351\]; int main() \{ int n,i,j; // freopen("

小鱼儿/ 2022年06月17日 23:29/ 0 赞/ 153 阅读

相关 HDU1695GCD 容斥

原来用莫比乌斯写过这个[传送门][Link 1]，发现这个用容斥挺好理解，就是跑的比莫比乌斯慢，莫比乌斯跑了40ms，这个跑了400ms。估计复杂度是O(n\6\2^6)大

Love The Way You Lie/ 2022年05月16日 02:55/ 0 赞/ 242 阅读

相关 poj1695 dp思维不错

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

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