首页 > 代码库 > 【NOIP】提高组2005 过河
【NOIP】提高组2005 过河
【算法】状态压缩型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=30000,maxm=110;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=1;i<=n;i++)scanf("%d",&a[i]); int ans=0; if(s==t) { for(int i=1;i<=n;i++)if(a[i]%s==0)ans++; printf("%d",ans); return 0; } sort(a,a+n+1); int ago=0,mark=0,p=t*(t-1)+1; for(int i=1;i<=n;i++) { if(a[i]-ago>=p) b[(mark+=p)]=1; else b[(mark=mark+a[i]-ago)]=1; ago=a[i]; } if(l-ago>p) mark+=p; else mark=mark+l-ago; memset(f,0x3f,sizeof(f)); f[0]=0; 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 0;}
【NOIP】提高组2005 过河
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。