主题：第46次编程比赛第一题
tiancai007 [专家分：0] 发布于 2006-10-27 21:31:00
船长哈里正计划着一次太空远行，他准备从他所在的星球前往距离L单位远的另一个星球。现假设在途中每过1个单位的距离便会抵达有一个中间站。由于飞船的油仓装的油有限，所以飞船一次飞行最多只能飞行max单位，然后降落中间站加油。又因为每次起飞的代价非常高，所以每次飞行距离必须大于等于min，然后降落加油。现在因为其中几个中间站附近有海盗出没，所以船长希望尽可能的避免这些有危险的中间站降落。
现给出距离L，min和max，有危险的中间站的位置（起点为0),你的任务就是帮助船长找出最优的方案，即降落在危险中间站的次数最少。
输入文件：
输入文件feichuan.in的第一行有一个正整数L（1 <= L <= 109）。第二行有三个正整数min，max，n，分别表示飞船一次飞行的最小距离，最大距离，及危险中间站的个数，其中1 <= min <= max <= 10，1 <= n <= 100。第三行有n个不同的正整数分别表示这n个危险中间站在数轴上的位置（数据保证的起点和终点处没有危险）。所有相邻的整数之间用一个空格隔开。
输出：
用printf输出一个整数，即经过有危险的中间站自少次数
样例输入
10
2 3 5
2 3 6 7 8
样例输出
2
数据规模
对于30%的数据，L <= 10000；
对于全部的数据，L <= 109（10的9次方）。
回复列表 （共15个回复）
沙发
FancyMouse [专家分：13680] 发布于 2006-10-27 23:03:00
- -||| 把去年noip提高组第2题，过河，加了个外壳而已- -
这个网上题解已经泛滥了……
这是去年比赛以后我的代码（比赛的时候只得了20分……一点小失误）
#include<iostream>
#include<cstring>
using namespace std;
const int MaxStones = 100;
int s,t;
const int MaxLen = 20000;
void Sort(int* array,int size);
int main()
{
int dest,stones;
cin>>dest>>s>>t>>stones;
int i,j;
int mul = s*t;
//input stone
int stone[MaxStones],elapsed;
for(i=0;i<stones;i++) cin>>stone[i];
Sort(stone,stones);
elapsed = stone[0];
if(stone[0] > mul) stone[0] = mul + stone[0]%mul;
int delta;
for(i=1;i<stones;i++)
{
delta = stone[i] - elapsed;
elapsed = stone[i];
if(delta > mul) delta = mul + delta%mul;
stone[i] = stone[i-1] + delta;
}
delta = dest - elapsed;
if(delta > mul) delta = mul + delta%mul;
dest = stone[stones-1] + delta;
//dp
int map[MaxLen],dp[MaxLen];
memset(map,0,sizeof(map));
for(i=0;i<stones;i++)
map[stone[i]] = 1;
memset(dp,-1,sizeof(dp));
dp[0] = 0;
for(i=0;i<dest;i++)
{
if(dp[i] < 0) continue;
for(j=s;j<=t;j++)
if(dp[i+j] < 0 || dp[i+j] > dp[i] + map[i+j])
dp[i+j] = dp[i] + map[i+j];
}
int result = 0x7fffffff;
for(i=0;i<t;i++)
if(dp[i+dest] >= 0 && dp[i+dest] < result)
result = dp[i+dest];
cout<<result<<endl;
return 0;
}
void Sort(int* array,int size)
{
for(int i=1;i<size;i++)
for(int j=0;j<i;j++)
if(array[j] > array[i])
{
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
板凳
neverPE [专家分：1620] 发布于 2006-10-28 09:42:00
哈哈，青蛙过河，状态压缩的DP。
LZ改得很有意思，比原来好玩多了：）
3 楼
bloodybg [专家分：1510] 发布于 2006-10-28 17:44:00
#include <stdio.h>
#include <stdlib.h>
int s, t;
int count = 0;
long curLen;
void ReadFile(int &l, int &m)
{
FILE *fp = fopen("1.txt", "r");
if (fp == NULL)
{
printf("Can not open file!\n");
exit(1);
}
fscanf(fp, "%d", &l);
fgetc(fp);
fscanf(fp, "%d", &s);
fgetc(fp);
fscanf(fp, "%d", &t);
fgetc(fp);
fscanf(fp, "%d", &m);
fgetc(fp);
curLen = ftell(fp);
fclose(fp);
}
void ReadArray(int m, int *a)
{
FILE *fp = fopen("1.txt", "r");
if (fp == NULL)
{
printf("Can not open file!\n");
exit(1);
}
fseek(fp, curLen, SEEK_SET);
for (int i = 0; i < m; i++)
{
fscanf(fp, "%d", &(a[i]));
fgetc(fp);
}
fclose(fp);
}
int gpp(int &sum, int temp, const int a[])
{
if (temp + sum < a[count] && temp < t)
{
sum += temp;
temp = s;
count ++;
return gpp(sum, temp, a);
}
else if (temp + sum == a[count] && temp < t)
{
count++;
return gpp(sum, ++temp, a);
}
else if (temp + sum == a[count] && temp == t)
{
count++;
sum += temp;
return 1;
}
else
{
count++;
sum += temp;
return 0;
}
}
int main()
{
int sum = 0, result = 0;
int l, m;
ReadFile(l, m);
int temp;
int a[100];
ReadArray(m, a);
while (sum < l)
{
temp = s;
result += gpp(sum, temp, a);
}
printf("%d\n", result);
return 0;
}
4 楼
mygoogle [专家分：500] 发布于 2006-10-28 18:14:00
难!
5 楼
zujay [专家分：0] 发布于 2006-10-28 18:51:00
悲惨 ！！！ 打击我信心
6 楼
redlives [专家分：6090] 发布于 2006-10-28 20:49:00
头一次参加，主要是学习学习，做的不对大家不要见笑。
#include <iostream.h>
#include <fstream>
#include <string>
using namespace std;
int L = 0;
int max = 0,min = 0,n = 0,times = 0;
int finddanger(int *temp)
{
int i,k,m;
for(i = 0,k = 0;i < L;i ++)
{
if(i != min)
m = 0;
else
m = 1;
for(; k < n;k ++,m ++,i ++)
{
if(temp[k] != i)
{
break;
}
}
times += m / max;
}
return 1;
}
int main(int argc, char* argv[])
{
ifstream infile;
infile.open("feichuan.in");
if(!infile)
{
cout << "ERROR!" << endl;
}
infile >> L;
infile >> min;
infile >> max;
infile >> n;
int *a = new int[n];
for(int i = 0;i < n;i ++)
{
infile >> a[i];
}
if(max == min)
{
for(i = 0;i < n;i ++)
{
if(a[i] % max == 0)
times ++;
}
}
else
finddanger(a);
infile.close();
cout << "需要次数为：" << times << endl;
delete []a;
return 0;
}
7 楼
bloodybg [专家分：1510] 发布于 2006-10-28 20:51:00
发错了
再发一次
#include <stdio.h>
#include <stdlib.h>
int l, s, t, m;
int count = 0;
int a[100];
long curLen;
void ReadFile()
{
FILE *fp = fopen("1.txt", "r");
if (fp == NULL)
{
printf("Can not open file!\n");
exit(1);
}
fscanf(fp, "%d", &l);
fgetc(fp);
fscanf(fp, "%d", &s);
fgetc(fp);
fscanf(fp, "%d", &t);
fgetc(fp);
fscanf(fp, "%d", &m);
fgetc(fp);
curLen = ftell(fp);
fclose(fp);
}
void ReadArray()
{
FILE *fp = fopen("1.txt", "r");
if (fp == NULL)
{
printf("Can not open file!\n");
exit(1);
}
fseek(fp, curLen, SEEK_SET);
for (int i = 0; i < m; i++)
{
fscanf(fp, "%d", &(a[i]));
fgetc(fp);
}
fclose(fp);
}
int IsInArray(int temp)
{
if (temp >= l)
return 0;
for (int i = 0; i < m; i ++)
{
if (temp == a[i])
return 1;
}
return 0;
}
int gpp(int &sum, int temp)
{
if (sum >= l)
return 0;
if (!IsInArray(temp + sum) && temp < t)
{
sum += temp;
temp = s;
while (sum > a[count])
count ++;
return gpp(sum, temp);
}
else if (IsInArray(temp + sum) && temp < t)
{
while (sum > a[count])
count ++;
return gpp(sum, ++temp);
}
else if (IsInArray(temp + sum) && temp == t)
{
sum += temp;
while (sum > a[count])
count ++;
return 1;
}
else
{
sum += temp;
while (sum > a[count])
count ++;
return 0;
}
}
int main()
{
int sum = 0, result = 0;
ReadFile();
int temp;
ReadArray();
while (sum < l)
{
temp = s;
result += gpp(sum, temp);
}
printf("%d\n", result);
return 0;
}
8 楼
liyitong [专家分：0] 发布于 2006-10-28 21:11:00
难
9 楼
liyitong [专家分：0] 发布于 2006-10-28 21:12:00
看看
10 楼
thomas [专家分：180] 发布于 2006-10-28 22:06:00
noip2005的题吧，dp加离散了
ps: 应该都做过吧
我来回复
您所在位置：