我觉得这题在 luogu 上难度评级不正常，它应该不只是一个绿题...
做题的时候遇到的，感觉可以算是一种新的 dp 优化方式。
题目链接
题意
现在有一个独木桥，起点为 ，终点为 ，这个独木桥上一共有 个石头。
现在有一只青蛙在
的位置，它每一次跳跃可以使自己的位置增加 中的一个整数。
现在这只青蛙想要跳到
的位置，请问它最少需要踩到多少块石头。
题解
首先我们会发现，如果本题的
比较小，那么我们可以直接通过 dp 来解决。
方程为：。
这样我们能拿到 分。
再次观察数据范围，我们发现
三个量都很小。
尤其是
这两个量，格外突出。
首先我们可以特判
的情况，这种情况我们可以直接算出答案。
对于剩下的情况，我们会发现，对于一个很大的距离 ，即使我们每一次只向前跳 或 的距离，我们也可以恰好“凑出”一个
。
这就告诉我们，假如两块石头之间的距离比较大，我们可以手动把它们之间的距离缩小。
那么具体缩小多少呢？
一种可行的思路每一次缩短 ，它是 。
还有一种思路就是 ，因为所有
的数字都可以使用任意相邻两个数“凑”出来。
时间复杂度是 。
我的代码中取的是 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
bool vis[30001];
int dp[30001];
int pre[102];
int a[102];
int l,s,t,n;
int main()
{
l=read(),s=read(),t=read(),n=read(),a[n+1]=l;
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
if(s==t)
{
int ans=0;
for(int i=1;i<=n;i++) if(a[i]%s==0) ans++;
printf("%d\n",ans);
return 0;
}
for(int i=1;i<=n+1;i++)
{
pre[i]=a[i]-a[i-1];
if(pre[i]>=72) pre[i]=pre[i]%72+72;
}
for(int i=1;i<=n;i++) a[i]=a[i-1]+pre[i],vis[a[i]]=1;
l=a[n]+pre[n+1];
memset(dp,0x3f,sizeof(dp)),dp[0]=0;
for(int i=1;i<=l;i++) for(int j=s;j<=t&&j<=i;j++) dp[i]=min(dp[i],dp[i-j]+vis[i]);
int ans=0x3f3f3f3f;
for(int i=a[n];i<=l;i++) ans=min(ans,dp[i]);
printf("%d\n",ans);
return 0;
}
|
感谢观看！