首页 > 代码库 > 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,滚动数组,离散化]