过河

题目传送门

解题思路

这题就是状态压缩优化
你可以先去看看P3951 小凯的疑惑（数论）
从上题得知，a*b-a-b是最大不能得到的价值，后面的价值都能够得到
这题也大同小异，当奇数和偶数都可以被枚举到时，后面的数自然也可以被枚举到
最大能枚举到奇数和偶数的位置，就是T * (T-1)，这样就可以压缩空间和运算次数

	for(int i=1; i<=m; i++)
    {
   
     	b[i]=min(a[i]-a[i-1],90);//最多是10*（10-1）=90
     	l+=b[i];//重新统计长度
     	sum[l]=1;//标记石头位置
    }

DP

用一个 f[i]
表示当前第 i 个点走过了 x 个石头。
f [ i ] = m i n ( f [ i ] , f [ i − j ] + s u m [ i ] ) ; f[i]=min(f[i],f[i−j]+sum[i]); f[i]=min(f[i],f[i−j]+sum[i]);

AC代码

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int l,s,t,m,a[105],b[105],sum[10000005];
long long answer,f[10000005];
int main()
{
   
    scanf("%d",&l);
    scanf("%d%d%d",&s,&t,&m);
    for(int i=1;i<=m;i++)
    {
   
     	scanf("%d",&a[i]);
     	if(a[i]%s==0)answer++;
    }
    if(s==t)//特判
    {
   
     	cout<<answer;
     	return 0;
    }
    sort(a+1,a+1+m);//快排
    b[m+1]=min(l-a[m],90);//初值
    l=0;
	for(int i=1; i<=m; i++)
    {
   
     	b[i]=min(a[i]-a[i-1],90);//最多是10*（10-1）=90
     	l+=b[i];//重新统计长度
     	sum[l]=1;//标记石头位置
    }
    l+=b[m+1];//累加
    for(int i=1;i<=l+9;i++)//dp
    {
   
     	f[i]=2147483647;//初值
     	for(int j=s;j<=t;j++)
     	 if(i>=j)
		  f[i]=min(f[i],f[i-j]+sum[i]);//状态转移
    }
    answer=2147483647;
    for(int i=l;i<=l+9;i++)//找最小
     answer=min(answer,f[i]);
    printf("%d",answer);
    return 0;
}

谢谢