## sgu 183 - DP，滚动数组 原

m2012

``````#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
template <class VVType, class T>
void make2DVector(VVType & a, int d, int f, const T & initValue) {
int i, j;
a.resize(d);
for (i = 0; i < d; ++i) {
a[i].resize(f);
for (j = 0; j < f; ++j) a[i][j] = initValue;
}
}

template <class VType, class T>
void makeVector(VType & a, int len, const T & initV) {
a.resize(len);
int i;
for (i = 0; i < len; ++i) a[i] = initV;
}

inline int mod256(int x) {
// assert(x >= 0);
return x & 255;
}

// 全局函数 ====================================================

vector< vector<int> > f;
vector< vector<int> > g;
int N;
int M;
vector< int > c;

//===============================================================

inline int dist(int a, int b) {
if (a >= b) return a - b;
return b - a;
}

void dp() {
int i, j;

for (i = 2; i <= N; ++i) {

for (j = i - 1; j >= 1 && dist(i, j) <= M; --j) {
if (i <= M) {
f[mod256(i)][mod256(j)] = c[i] + c[j];
continue;
}

f[mod256(i)][mod256(j)] = g[mod256(j)][mod256(i - M)] + c[i];
}

g[mod256(i)][mod256(i - 1)] = f[mod256(i)][mod256(i - 1)];
for (j = i - 2; j >= 1 && dist(j, i) <= M; --j) g[mod256(i)][mod256(j)] = min(g[mod256(i)][mod256(j + 1)], f[mod256(i)][mod256(j)]);
}

int ans = 2000000000;
for (i = N; i >= 2 && i >= N - M + 2; --i) {
for (j = i - 1; j >= 1 && j >= N - M + 1; --j) {
if (ans > f[mod256(i)][mod256(j)]) ans = f[mod256(i)][mod256(j)];
}
}

printf("%d\n", ans);
}

void input() {
scanf("%d %d", &N, &M);
int i;
makeVector(c, N + 3, 0);
for (i = 1; i <= N; ++i) scanf("%d", &(c[i]));

make2DVector(f, 256, 256, 0);

make2DVector(g, 256, 256, 0);
}

int main() {
input();
dp();
return 0;
}``````

### m2012

NYOJ ~ 1273 ~ 宣传墙

zscdst
2018/04/03
0
0

03/02
0
0

2018/06/12
0
0
[线性DP][codeforces-1110D.Jongmah]一道花里胡哨的DP题

fanwenlin
02/10
0
0

2018/01/17
0
0

Java单例模式学习记录

JerryLin123

2
0
VSCODE 无法调试

VSCODE 无法调试 可以运行 可能的原因： GCC 的参数忘了加 -g

shzwork

3
0

Tiny熊

4
0
5.线程实现

Eappo_Geng

4
0