// [解题方法]
// 记忆化搜索(递归,子问题的结果用备忘录存起来,避免重复求解)
// 二维nxt数组按照题意记录路径
// dp[x][y](即dfs(x,y))表示从(x,y)走到最右边需要的最小花费
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define LL long long
#define inf 1e16
LL dp[11][111],w[11][111], mins, res[105];
int r, c;
struct point{
int x, y;
}nxt[11][111];
LL dfs (int x, int y)
{
if (y >= c) return (dp[x][y]=w[x][y]);
if (dp[x][y] < inf)
return dp[x][y];
int i;
LL tp = inf;
for (i = x-1; i <= x+1; i++)
{
int tr = i;
if (tr == 0) tr = r;
else if (tr > r) tr = 1;
LL tmp = dfs (tr, y+1) + w[x][y];
//更新路径(花费更小+字典序)
if (tmp < tp || (tmp == tp && tr < nxt[x][y].x)) {
nxt[x][y].x = tr;
nxt[x][y].y = y+1;
tp = tmp;
}
}
return (dp[x][y]=tp);
}
int main()
{
int i, j;
while (cin >> r >> c)
{
for (i = 1; i <= r; i++)
for (j = 1; j <= c; j++)
cin >> w[i][j], dp[i][j] = inf;
mins = inf;
int v;
memset (nxt, -1, sizeof(nxt));
for (i = 1; i <= r; i++)
{
LL tp = dfs (i, 1);
if (tp < mins) {
mins = tp;
v = i;
}
}
int tc = 1, k = 0;
while (v > 0)
{
res[k++] = v;
int tv = v;
v = nxt[tv][tc].x;
tc = nxt[tv][tc].y;
}
cout << res[0];
for (i = 1; i < k; i++) cout << ' ' << res[i];
cout << endl << mins << endl;
}
return 0;
}
分享到:
相关推荐
Minimizing AMDs in unidirectional WDM rings with grooming factor 6,徐允庆,常彦勋,In wavelength division multiplexing for unidirectional rings, traffic grooming is used to pack low rate signals ...
Unidirectional edge modes launched by surface fluctuation in magnetic metamaterials
ERP信息化系统:SAP学习资料文档SOH-R3- IT Proposal-Unidirectional Blueprint-122906 v10.5.ppt
具分布时滞的单向神经网络模型的分支分析,韩艳艳,宋永利,在这篇文章中,我们研究了分布时滞对三元环形神经网络系统的动力学的影响。以平均时滞为参数,我们得到了两个Hopf分支的临界值。 用�
We demonstrate a single-longitudinal-mode Ho3+:YVO4 unidirectional ring laser based on the acousto-optic effect, utilizing the features of the acousto-optical Q switch and half-wave plate to achieve ...
海桑属、木榄属和橐吾属单向杂交方向假说的检验,周仁超,施苏华,当丰富度不同的物种发生杂交时,授到稀有物种上的花粉主要来自于常见物种。以前的学者对杂交方向提出了一个假说:物种间的杂交通
Recent experiments demonstrated that chiral symmetry breaking at an exceptional point (EP) is a viable route to achieve unidirectional laser emission in microring lasers. By a detailed semiconductor ...
Efficient Unidirectional Launching of Surface Plasmons by Multi-Groove Structures
At ACNS 2007, Ateniese and Green proposed the concept of ID-based proxy re-encryption (IBPRE), where a semi-trusted proxy with some information (a.k.a. re-encryption key), can transform a ...
新型超高温铌基固溶体—铌硅化物共晶自生复合材料的定向凝固,郭喜平,管萍,研究了多元合金化的铌基超高温合金在电子束区熔炉上的定向凝固组织、室温断裂韧性及室温拉伸性能。
Efficient unidirectional launching of surface plasmons by a cascade asymmetric-groove structure
Fusing electromagnetic one-way edge states to achieve broadband unidirectional wave transmission
A simple method for generating unidirectional surface plasmon polariton beams with arbitrary profiles
Gaussian beam is incident to a magnetic metamaterial (MM) slab, it can be completely absorbed at a particular direction, resulting in a unidirectional perfect absorption. The unidirectionality is due ...
A simplified ring cavity for achieving a unidirectional room temperature multi-wavelength erbium-doped fiber ring laser without optical isolator is demonstrated. The fiber ring cavity is built in such...
A short distributed feedback fiber laser with a nearly unidirectional output is fabricated and tested. The short fiber laser is made of a polarization-dependent phase-shift grating fabricated with a ...
We present an experimental study on a unidirectional surface plasmon polariton (SPP) launcher based on a compact binary area-coded nanohole array, where the symmetry breaking is realized via effective...
It is demonstrated that laser output of the Erbium-Ytterbium co-doped fiber under the bi-directional pumping regime is more stable than that under the unidirectional pumping one due to the relatively...
Delphi的UniDAC控件 使用说明,
单向 Elm体系结构,用于JavaScript中的用户界面开发。 运行一个例子 # npx grunt start-example --example= npx grunt start-example --example=gif-list 在浏览器中访问 。 使用doc/examples目录中的任何目录...