【算法】状态压缩型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 ;
}

最新文章

  1. C代码实现非循环单链表
  2. codeforces 724D(贪心)
  3. JSP 和 ASP.NET 谁能主宰未来【转】
  4. node基础 --全局
  5. 透过c的编程原则,来规范自己现在的一些编程习惯
  6. 车牌识别LPR系统系列文章汇总
  7. 树形DP+树状数组 HDU 5877 Weak Pair
  8. apache开源项目--Sirona
  9. JAVA打印类(带预览)
  10. sql server 深入使用 总结 part1
  11. HDU 2451 Simple Addition Expression(组合数学)
  12. ArrayList源码学习
  13. IntelliJ IDEA最新破解版2018.3.1(附2018.2.2 完美破解教程)
  14. shell-特殊变量列表
  15. C#中方法、类等的默认访问修饰符~
  16. JWT学习小结
  17. PHP爬虫框架Snoopy的使用
  18. 获取日期Date
  19. 【转】10个非常有用的网页设计工具 | Goodfav Magazine
  20. thinkCMF----路由跳转

热门文章

  1. # 团队作业MD
  2. alpha-4
  3. headers的描述
  4. CentOS修改DNS、IP地址、网关
  5. PHP实现大文件分割上传与分片上传
  6. js获取某周、某月、下月、某季度的开始日期、结束日期及判断日期第几周
  7. iOS-开发中的时间处理
  8. 【刷题】洛谷 P2709 小B的询问
  9. [洛谷P4962]朋也与光玉
  10. [洛谷P3833][SHOI2012]魔法树