[vijos1002]-[NOIP2005]过河

发布于 2017-09-12  25 次阅读



题目(vijos)
这题先看题:不用说,简直水的dp。
然后再看数据范围......
呵呵。
 
 
那么这题该怎么去做呢?
dp方程其实很好推,设b数组是用来存第i个点是否有石子,
所以方程为:dp[i]=min(dp[i],dp[i-j]+b[i]),其中s<=j<=t。
但是这个L<=10^9……
不用急,看看m的范围:m<=100。
什么意思呢?就是说在这段很长的桥中,只有100个点有石子。
这就表明:有很多空点,很多的空点我们是不用考虑的。
于是可以压缩状态。
我们再发现,t最多只有10,所以这里就是个比较玄学的方法了:每两个石子之间的长度取模100或者更多,变为新的距离。这样,很多的空点就可以去除掉了。
为什么可以这样?
可以感受一下:两者之间的有效距离<=s*t,具体证明有点复杂,暂时不写。
然后就做完啦~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int l,s,t,m;
int a[105];
int dp[2000005];
int b[2000005];
int ans=0x3f3f3f3f;
int main()
{
	memset(dp,63,sizeof dp);
	dp[0]=0;
	scanf(
	for (int i=1;i<=m;++i)
		scanf(
	sort(a+1,a+m+1);
	if (s==t)
	{
		int tot=0;
		for (int i=1;i<=m;++i)
			if (a[i
		printf(
		return 0;
	}
	for (int i=1;i<=m;++i)
	{
		int dis=a[i]-a[i-1];
		a[i]=a[i-1]+di
	}
	l=(l-a[m]
	for (int i=1;i<=m;++i)
		b[a[i]]=1;
	for (int i=s;i<=l+t;++i)
	{
		for (int j=s;j<=t;++j)
		{
			if (i>=j)
			dp[i]=min(dp[i],dp[i-j]+b[i]);
		}
	}
	for (int i=l;i<=l+t;++i)
		ans=min(ans,dp[i]);
	printf(
	return 0;
}