洛谷 P1052 过河
思路部分可以看这篇博客
我将在这里对其进行一些解释与补充
首先我们先看题
乍一看
这不是模板题吗
然后开开心心的敲了一个简单dp上去
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e6;
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return f*ret;
}
long long n;
int vis[maxn];
int s,t,m;
int dp[maxn];
int main(){
// freopen("a.in","r",stdin);
n=read();
s=read();
t=read();
m=read();
int x;
for(int i=1;i<=m;i++){
x=read();
// cin>>x;
vis[x]=1;
}
for(int i=1;i<=n+t-1;i++){
dp[i]=0x3f3f3f;
}
dp[0]=0;
for(int i=1;i<=n+t-1;i++){
int k;
if(i-s>=0){
if(i<=t)
k=0;
else{
k=i-t;
}
for(int j=k;j<=i-s;j++){
dp[i]=min(dp[i],dp[j]+vis[i]);
}
}
else continue;
}
int ans=0x3f3f3f3f;
for(int i=n;i<=n+t-1;i++){
if(ans>dp[i])
ans=dp[i];
}
cout<<ans;
return 0;
}
然后就喜提 30分
仔细一看题目
数据范围1e9,自然
我们需要对dp进行优化
我们再一看，石子的数量小于等于100，便想到了路径压缩（我是废物，没想到）
至于怎样路径压缩，上面那篇博客有讲，我在此进行一些解释与补充
先贴我的代码吧
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e6;
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return f*ret;
}
long long n;
int a[maxn];
int s,t,m;
int v[maxn];
int dp[maxn];
int main(){
n=read();
s=read();
t=read();
m=read();
for(int i=1;i<=m;i++){
a[i]=read();
}
if(s==t){
int ans=0;
for(int i=1;i<=m;i++){
if(a[i]%s==0)
ans++;
}
cout<<ans;
return 0;
}
sort(a,a+1+m);
int cnt=0;
for(int i=1;i<=m;i++){
int l=a[i]-a[i-1];
if(l>=t){
cnt+=l%t+t;
}
else {
cnt+=a[i]-a[i-1];
}
v[cnt]=1;
}
memset(dp,0x3f3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=cnt+t-1;i++){
int e;
if(i-s>=0){
if(i<=t)
e=0;
else{
e=i-t;
}
for(int j=e;j<=i-s;j++){
dp[i]=min(dp[i],dp[j]+v[i]);
}
}
else continue;
}
int ans=0x3f3f3f3f;
for(int i=cnt;i<=cnt+t-1;i++){
if(ans>dp[i])
ans=dp[i];
}
cout<<ans;
return 0;
}
这里我要解释几点
1，青蛙只要跳出这个桥，就算过河了，没必要经过桥的终点
所以观察我们最后选最小的过程，就可以发现我们的边界为cnt+t-1
2，我们通过路径压缩，在到达性不变的前提下，缩小讨论长度，缩小原本数据范围，达到时间优化
优化后就转变为较为简单的DAG上的dp;
3，路径压缩的方法较多，我们本质上要保证压缩后的可到性，也就是说，不能采取压缩前一点可到，压缩后不可到的情况，由此可知，我们将模数改为s便为错误情况（至于我为什么知道，因为我改完后wa了）