首页 > 代码库 > vijos 1002过河[单调dp,滚动数组,离散化]
vijos 1002过河[单调dp,滚动数组,离散化]
这道题是NOIP第一道DP优化题,看似容易,实际上想要满分也颇有难度。
传送门:1002 过河
算法
此题显然要用到DP,DP方程也显而易见:
if (stone[i]) f[i]=min{f[i-j]}+1; (S<=j<=T)
else f[i]=min{f[i-j]};
这样的时间复杂度为 O(LT) ,空间复杂度为 O(L) 。
而此题的L高达 10亿 ,所以这种朴素的方法只能得 30分 ,显然无法AC。
优化
1.滚动数组
根据我们得出的DP方程,状态转移只需用到 f[i-T]~f[i-S] 的值,所以只需开大小为T的滚动数组即可。
所以空间复杂度被优化到了 O(T) 。由于T小于等于10,所以空间上显然没有问题。
2.离散化DP
看了看别人的题解,发现有人选择压105位来优化,这种方法虽然能过,但是或多或少有投机取巧的嫌疑,毕竟比赛时谁知道去压正好105位呢?
所以我们必须想出一般性的方法。我们会发现,石头的个数M远远小于长度L,不禁让我们想到了离散化——当S<T且有一大段桥没有石头时,常常会出现整个滚动数组f的值一样的情况,这时我们可以在遇到下一颗石头之前不再改变f的值,从而达到优化的效果。
在下用tot变量记录当前数值连续出现的次数,如果超过T次,则将i直接跳转到下一个石头的位置之前,从而提高效率。
优化后,时间复杂度降至 O(MT) ,已经达到了AC的要求。
特判
上面的离散化显然建立在S<T的基础上。如果S==T,那么永远达不到优化的条件,优化就不会奏效,从而 *TLE:90分 * 。
因此我们必须加上特判,当S==T时,ans就是位置为T的倍数的石头的数量。虽然简单,却十分考验选手思维的严密性。
代码:
#include<cstdio> #include<cstring> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; int dp[100]; int r[200]; inline int min(int a,int b) { return a<b?a:b; } int main() { int L,s,e,m; scanf("%d%d%d%d",&L,&s,&e,&m); for(int i=0;i<m;i++) scanf("%d",r+i); sort(r,r+m); memset(dp,INF,sizeof dp); int p=0,tot=0,now=0; dp[0]=0; if(s==e) { int ans=0; for(int i=0;i<m;i++) if(r[i]%e==0) ans++; printf("%d\n",ans); return 0; } for(int i=1;i<=L;i++) { for(int j=s;j<=e;j++) { dp[i%e]=min(dp[i%e],dp[(i-j+e)%e]); //滚动数组,下标0-(t-1) } if(i==r[p]) //记录是否有石头,想想用vis标记,实在太逗! { dp[i%e]++; p++; } if(now==dp[i%e]) // 离 tot++; else { now=dp[i%e]; tot=0; // 散 } if(tot==e) { i+=(min(r[p]-e,L)-i)/e*e; } // 化 } printf("%d\n",dp[L%e]); return 0; }
vijos 1002过河[单调dp,滚动数组,离散化]