文档章节

sgu 183 - DP,滚动数组

m2012
 m2012
发布于 2012/05/13 11:42
字数 320
阅读 206
收藏 0

这题要好好总结一下,有太多东西要学了,先开个坑

#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
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
NYOJ ~ 1273 ~ 宣传墙

思路:n比较大为1e6,dp[1e6][1<<4]的数组开不下,我们可以发现i的状态都是由i-1得到的,所以我们可以用滚动数组进行优化,但是记得需要清空。i^1可以实现0变为1, 1变为0。 其实呢正解是矩阵...

zscdst
2018/04/03
0
0
牛客练习赛 41 B 题 【简单的dp计数】

版权声明:本文为博主原创文章,喜欢就点个赞吧 https://blog.csdn.net/Anxdada/article/details/88071477 传送门 题意: 就n个数,开始分数为0, 第i次操作可以有两种选择 1: 给分数加上a[i] ...

Anxdada
03/02
0
0
面试题解| coins in a line iii 区间DP

专栏 | 九章算法 网址 | http://www.jiuzhang.com 题 coins in a line iii 区间DP 题目描述 有 n 个硬币排成一条线,每一枚硬币有不同的价值。两个参赛者轮流从任意一边取一枚硬币,直到没有硬...

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

题目来源: Codeforces - 1110D 题意:你有n张牌(1,2,3,...,m)你要尽可能多的打出[x,x+1,x+2] 或者[x,x,x]的牌型,问最多能打出多少种牌 思路: 1.三组[x,x+1,x+2]的效果等同于 [x,x,x...

fanwenlin
02/10
0
0
求两个数组的最长重复子数组 Maximum Length of Repeated Subarray

问题: Given two integer arrays and , return the maximum length of an subarray that appears in both arrays. Example 1: Input:A: [1,2,3,2,1]B: [3,2,1,4,7]Output: 3Explanation:The......

叶枫啦啦
2018/01/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java单例模式学习记录

在项目开发中经常能遇见的设计模式就是单例模式了,而实现的方式最常见的有两种:饿汉和饱汉(懒汉)。由于日常接触较多而研究的不够深入,导致面试的时候被询问到后有点没底,这里记录一下学习...

JerryLin123
昨天
2
0
VSCODE 无法调试

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

shzwork
昨天
3
0
理解去中心化 稳定币 DAI

随着摩根大通推出JPM Coin 稳定币,可以预见稳定币将成为区块链落地的一大助推器。 坦白来讲,对于一个程序员的我来讲(不懂一点专业经济和金融),理解DAI的机制,真的有一点复杂。耐心看完...

Tiny熊
昨天
4
0
5.线程实现

用于线程实现的Python模块 Python线程有时称为轻量级进程,因为线程比进程占用的内存少得多。 线程允许一次执行多个任务。 在Python中,以下两个模块在一个程序中实现线程 - _thread 模块 th...

Eappo_Geng
昨天
4
0
ServiceLoader

创建一个接口文件在resources资源目录下创建META-INF/services文件夹在services文件夹中创建文件,以接口全名命名创建接口实现类 内容me.zzp.ar.d.PostgreSQLDialectme.zzp.ar.d.Hype...

Cobbage
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部