【NOIP】提高组2005 过河
2024-08-27 23:38:43
【算法】状态压缩型DP
【题解】
Q=tx+(t-1)y
对于Q≥t(t-1),x,y一定有解。
所以当两石子间距离long>t(t-1)时,令long=t(t-1),重新构造数组即可。
【注意】
1.输入的石子位置无序,要排序。
2.当s=t时特判。
3.最终解要在n~n+t中找最小值(不过数据太水=v=)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxm=;
int a[maxm],b[maxn],f[maxn],l,s,t,n;
int main()
{
scanf("%d%d%d%d",&l,&s,&t,&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
int ans=;
if(s==t)
{
for(int i=;i<=n;i++)if(a[i]%s==)ans++;
printf("%d",ans);
return ;
}
sort(a,a+n+);
int ago=,mark=,p=t*(t-)+;
for(int i=;i<=n;i++)
{
if(a[i]-ago>=p)
b[(mark+=p)]=;
else b[(mark=mark+a[i]-ago)]=;
ago=a[i];
}
if(l-ago>p)
mark+=p;
else mark=mark+l-ago;
memset(f,0x3f,sizeof(f));
f[]=;
for(int i=s;i<=mark;i++)
for(int j=s;j<=t;j++)
{
f[i]=min(f[i],f[i-j]+b[i]);
}
/* for(int i=0;i<=mark;i++)printf("%d ",i);printf("\n");
for(int i=0;i<=mark;i++)printf("%d ",b[i]);printf("\n");
for(int i=0;i<=mark;i++)if(f[i]>1000)printf("x ");else printf("%d ",f[i]);*/
printf("%d",f[mark]);
return ;
}
最新文章
- C代码实现非循环单链表
- codeforces 724D(贪心)
- JSP 和 ASP.NET 谁能主宰未来【转】
- node基础 --全局
- 透过c的编程原则,来规范自己现在的一些编程习惯
- 车牌识别LPR系统系列文章汇总
- 树形DP+树状数组 HDU 5877 Weak Pair
- apache开源项目--Sirona
- JAVA打印类(带预览)
- sql server 深入使用 总结 part1
- HDU 2451 Simple Addition Expression(组合数学)
- ArrayList源码学习
- IntelliJ IDEA最新破解版2018.3.1(附2018.2.2 完美破解教程)
- shell-特殊变量列表
- C#中方法、类等的默认访问修饰符~
- JWT学习小结
- PHP爬虫框架Snoopy的使用
- 获取日期Date
- 【转】10个非常有用的网页设计工具 | Goodfav Magazine
- thinkCMF----路由跳转