Climber.pI的OI之路

Through the darkest dark，may we see the light.

NOIp 2005 过河

线性dp，但是范围很变态. = =

30%的方程很容易想到:
[状态] f[i]表示从0到i点最少踩到的石子数, stone[i]表示i点有无石子;
[方程] f[i] = max{f[i-j] + stone[i]} (S<=j<=T)
[初始化] f[0] = 0, 其他赋值为无限大.

在实现的时候需要把方程变化为 f[i+j] = max{f[i] + stone[i+j]}，不然在[1,S]会出现很诡异的结果.
 
由于m远远小于l，整个序列上的石子非常稀疏.所以可以减少状态.但是目前对此还是有些不解.
某种思路是，将石子间距大[1,2,..,9,10]=2520的逐次减至小于2520.注意要在收尾增加0和l两个"石子"，这样计算新的l较为方便.

 1#include<stdio.h>
 2#include<iostream>
 3using namespace std;
 4#define MAXN 1000000;
 5bool L[200000] = {0};
 6int f[200000] = {0}, stone[110] = {0};
 7int min(int x, int y){return x < y ? x : y;}
 8void swap(int x, int y){
 9    int k = stone[x];
10    stone[x] = stone[y];
11    stone[y] = k;
12}
13int main(){
14    int l, S, T, M, i, j;
15    scanf("%d%d%d%d", &l, &S, &T, &M);
16    for (i = 1; i <= M; i++) scanf("%d", &stone[i]);
17    stone[0] = 0;
18    for (i = 1; i < M; i++)
19        for (j = i+1; j <= M; j++)
20            if (stone[i] > stone[j]) swap(i, j);
21    stone[++M] = l;
22    for (i = 1; i <= M; i++){
23        while (stone[i] - stone[i-1] > 2520) stone[i] -= 2520;
24        if (i != M) L[stone[i]] = 1;
25    }
26    l = stone[M--];
27    for (i = 0; i <= l; i++) f[i] = MAXN; f[0] = 0;
28    for (i = 0; i < l; i++)
29        for (j = S; j <= T; j++){
30            int k = i+j;
31            if (i + j >= l) k = l;
32            f[k] = min(f[k], f[i]+L[i]);
33        }
34    printf("%d\n", f[l]);
35}

posted on 2010-10-08 21:54 Climber.pI 阅读(795) 评论(2)  编辑 收藏 引用 所属分类: 动态规划

Feedback

# re: NOIp 2005 过河 2010-10-09 08:53 ftiasch

2520恰好是1, 2, ..., 10的最小公倍数。原理就是可以证明说状态函数的值肯定会出现大段的重复。在理论上可以保证的就是2520。更多的分析应该用裴蜀定理来做。  回复  更多评论   

# re: NOIp 2005 过河 2011-09-08 13:30 PZYR

#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXN 1000000;
bool L[200000] = {0};
int f[200000] = {0}, stone[110] = {0};
int min(int x, int y){return x < y ? x : y;}
void swap(int x, int y){
int k = stone[x];
stone[x] = stone[y];
stone[y] = k;
}
int main(){
int l, S, T, M, i, j;
scanf("%d%d%d%d", &l, &S, &T, &M);
for (i = 1; i <= M; i++) scanf("%d", &stone[i]);
stone[0] = 0;
for (i = 1; i < M; i++)
for (j = i+1; j <= M; j++)
if (stone[i] > stone[j]) swap(i, j);
stone[++M] = l;
for (i = 1; i <= M; i++){
while (stone[i] - stone[i-1] > 2520) stone[i] -= 2520;
if (i != M) L[stone[i]] = 1;
}
l = stone[M--];
for (i = 0; i <= l; i++) f[i] = MAXN; f[0] = 0;
for (i = 0; i < l; i++)
for (j = S; j <= T; j++){
int k = i+j;
if (i + j >= l) k = l;
f[k] = min(f[k], f[i]+L[i]);
}
printf("%d\n", f[l]);
}  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理