设计网站建设图片,漳浦网站设计,安阳市最新消息,免费网页空间申请状态压缩的经典题。 按照一般做法#xff0c;DP一维时间O(n)#xff0c;显然跑不过。考虑到石子较少#xff0c;实际上有很长一段是一定可以跳到的#xff0c;设两个石头分别在i点和j点#xff0c;跳跃的路程为S到T。那么从i点可以跳到iS到iT。从j-T到j-S可以跳到J。显然当…状态压缩的经典题。 按照一般做法DP一维时间O(n)显然跑不过。考虑到石子较少实际上有很长一段是一定可以跳到的设两个石头分别在i点和j点跳跃的路程为S到T。那么从i点可以跳到iS到iT。从j-T到j-S可以跳到J。显然当i和j相隔非常非常远时从i到iT中必然可以经过若干次跳跃然后跳到j-T到j的任意一段。 然后状压可以发现距离大于90(假设s和t不同s(9)和t(10)的最小公倍数)一定可以到达这样我们把石头之间的距离%90节省时间。 然后特判一下st的情况就可以AC。但有一个问题我将mod变成100不特判st的情况这样会WA这个我无法理解。 数据100007 7 1001111 1118 1114 1117 3010 7508 1119 1105 899 1112 9667 3238 1108 5178 4627 2116 2089 9184 1115 8887 3565 3560 3559 3562 2410 3564 3571 565 3561 3566 3573 7432 9485 4484 7258 4555 8812 1291 3567 3221 5252 5253 5244 797 5251 7885 5245 9340 5255 6537 7737 5243 9316 5246 6694 6773 5247 6031 5256 5249 5484 5482 7513 5485 5479 5481 5480 5489 381 2572 9255 7624 5821 8606 7829 5488 442 5490 5492 8098 483 482 481 478 469 474 4054 472 471 4407 479 7006 475 470 3147 6933 9097 7781 473 2221应该输出10但是改了输出13. #includecstdio
#includeiostream
#includecstring
#includealgorithm
using namespace std;
int se[110],a[1100000],f[1100000];
int main()
{int L,s,t,n;scanf(%d%d%d%d,L,s,t,n);for(int i1;in;i)scanf(%d,se[i]);sort(se1,sen1);if(st){int ans0;for(int i1;in;i)if(se[i]%s0)ans;printf(%d\n,ans);return 0;}for(int i1;in;i)se[i]se[i-1](se[i]-se[i-1])%90;L(L-se[n])%90se[n];for(int i1;in;i)a[se[i]]1;memset(f,63,sizeof(f));f[0]0;for(int is;iLt;i)for(int js;jt;j)if(ij)f[i]min(f[i],f[i-j]a[i]);int ans999999999;for(int iL;iLt;i)ansmin(ans,f[i]);printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/AKCqhzdy/p/7616899.html
