跳至正文

[转]通过金矿模型介绍动态规划

  • 技术

对于动态规划,每个刚接触的人都需要一段时间来理解,特别是第一次接触的时候总是想不通为什么这种方法可行,这篇文章就是为了帮助大家理解动态规划,并通过讲解基本的01背包问题来引导读者如何去思考动态规划。本文力求通俗易懂,无异性,不让读者感到迷惑,引导读者去思考,所以如果你在阅读中发现有不通顺的地方,让你产生错误理解的地方,让你难得读懂的地方,请跟贴指出,谢谢!

—-第一节—-初识动态规划——–

经典的01背包问题是这样的:

有一个包和n个物品,包的容量为m,每个物品都有各自的体积和价值,问当从这n个物[……]

继续阅读

Web浏览 解题报告

  • OI路程

开到这个题目,想起了浏览器Lynx,用过两次,太难用了,汗,,貌似跑题了。
整个题目就是要了解一下浏览器的向前向后的特性,浏览器向后几步之后再输入网址就不能够向前浏览了。整个程序我就用一个数组来维护的,额,具体的细节看代码吧:

C语言:

#include <stdio.h>
#include <string.h>
#define MAX 10000
char link[MAX][71];
int tail, now;

void add(char *str)
{
 int t = (now[......]

继续阅读

谁拿了最多奖学金 解题报告

  • OI路程

这题我就什么都不说了吧,这题不会做你就回去把语言好好学学,学习输入输出的一些空格和换行。

C语言:

#include <stdio.h>
#define getint(i) scanf(%d, &i)

int main(void)
{
 int n, i;
 int t1, t2, t3;
 char c2, c1;
 int tot = 0;
 int max = 0;
 int grade;
 char maname[100], name[100];
 getint(n);
 for(i[......]

继续阅读

校门外的树 解题报告

  • OI路程

这题没什么好说的,我觉得就是用数组判断一下,我用memset优化了一些慢效率的循环,本来以为会超时,但是结果完全相反,速度还挺快。。
代码如下:

C语言:

#include <stdio.h>
#include <string.h>
char map[10001];

int main(void)
{
 int i, j;
 int a, b;
 int l, n;
 int ans = 0;

 scanf(%d%d, &l, &n);
 memset(map, 1, l[......]

继续阅读

Noip 2006 作业调度方案

  • OI路程

题目的原描述如下,rqnoj和vijos的题目都不完全,少了一幅图片,表格也不清晰。。

【问题描述】

我们现在要利用m台机器加工n个工件,每个工件都有m道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。

每个工件的每个工序称为一个操作,我们用记号j-k表示一个操作,其中j为1到n中的某个数字,为工件号;k为1到m中的某个数字,为工序号,例如2-4表示第2个工件第4道工序的这个操作。在本题中,我们还给定对于各操作的一个安排顺序。

例如,当n=3,m=2时,“1-1,1-2,2-1,3-[……]

继续阅读

金明的预算方案 解题报告

  • OI路程

这题刚拿到手,不知道怎么做,后来看到了题目里说每个主件最多有0,1,2个附件,那也就是说对于每个主件及其附件而言,最多有如下几种情况:不买一件;只买主件;买主件及附件1;买主件及附件2;买主件及附件1,2都买。
这么就好DP了,代码如下:

C语言:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[32001];
int v[61], p[61];
int lenth[61];
int have[61][2];
char n[......]

继续阅读

陶陶摘苹果 解题报告

  • OI路程

这种题目我确实不想写解题报告,没什么好写的,说它是贪心都不算,就是简单的模拟下。代码如下:

C语言:

#include <stdio.h>
int apples[10];

int main(void)
{
 int ans;
 int i, h;
 for(i = 0; i < 10; i++){
 scanf(%d, &apples[i]);
 }
 scanf(%d, &h);
 h += 30;
 for(i = ans = 0; i < 10; i++){
 if[......]

继续阅读

采药 解题报告

  • OI路程

就是一个经典的01背包,能够把时间看做体积,价值嘛就是价值,代码如下:

C语言:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[1001];

int main(void)
{
 int i, j;
 int m, n;
 int a, b;
 scanf(%d%d, &m, &n);
 for(i = 0; i < n; i++){
 scanf(%d%d, &a, &b);
 fo[......]

继续阅读

能量项链 解题报告

  • OI路程

额,花了我三四个小时的时间,终于知道了,是动态规划的题目(我以前做过,不过那个时候真是不知不觉过去的。),我以前只做过背包的题目,这个题目是这暑假以来觉得最复杂的题目了,因为非动态规划的代码一看就能看懂,动态规划的,方程没想通你就看不懂代码!
我的方程是:f[i][j] = max(f[i][k – i] + f[k][j – k + i] + boll[i] boll[i + j] boll[k])); 其中f[i][j]的意思是从i开始j个珠子的最大能量数,boll[i]是下标为i的珠子的能量。然后就是要注意[……]

继续阅读

数列 结题报告

  • OI路程

这一题先把顺序仔细观察一下,可以发现顺序就是n^0, n^1, n^0 + n^1, n ^ 2, n ^ 0 + n ^2….之类的数据,仔细观察能够发现顺序就是先输出n^i次方,再把所有的n^0 ~ n^i-1 和n^i进行相加。
嘿嘿,这题我倒是很自豪,发现了数学方法,仔细观察下,就可以发现第m个数字就是,n ^ log 2 (m) + n ^ log 2(m – 2 ^ log 2 (m)) + ….直到n^0为止,嘿嘿,代码如下:

C语言:

#include <stdio.h>
#in[......]

继续阅读