用vs2008做网站,本科学院网站建设方案,腾讯做的电子商务网站,桂林 网站建设[P1052 NOIP2005 提高组] 过河 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题描述#xff1a;给定长度L#xff0c;和一次可以跳动的长度 s 到 t#xff0c;给定m个石头的位置#xff0c;求最少经过多少个石头可以超过L。
思路#xff1a;如果L很小的话#xff0…[P1052 NOIP2005 提高组] 过河 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
问题描述给定长度L和一次可以跳动的长度 s 到 t给定m个石头的位置求最少经过多少个石头可以超过L。
思路如果L很小的话就是简单dp。 i f i 有石头 F ( i ) m i n ( F ( i ) , F ( i − j ) 1 ) j ∈ [ s , t ] e l s e F ( i ) m i n ( F ( i ) , F ( i − j ) ) j ∈ [ s , t ] if \quad i有石头 \quad F(i) min(F(i), F(i - j) 1) \quad j \in [s,t] \\ else \quad F(i) min(F(i), F(i-j)) \quad j \in [s,t] ifi有石头F(i)min(F(i),F(i−j)1)j∈[s,t]elseF(i)min(F(i),F(i−j))j∈[s,t] 但是发现L特别大但是石头个数却特别小同时也发现s和t也很小就算m * t * s最大也才1000。如果将石头距离进行缩小就可以过。
对于 两个石头距离大于s * t的来说对于区间[s * t, 两个石头之间的距离]都是可以经过跳[s, t]这些个数给到达的。因此可以将两个石头距离大于s * t的缩小为s * t这样就可以用上面的状态转移方程。
缩点 int st s * t;rep(i,1,m) {int dist a[i] - a[i-1];if(dist st) dist st;ph[i] ph[i-1] dist;// 将石头所在的那个点进行赋值为 truevis[ph[i]] 1;}状态转移方程 int len ph[m] st; memset(f, 0x3f, sizeof(f));f[0] 0;rep(i,1,len) {rep(j,s,t) {if(i - j 0) {if(vis[i]) f[i] min(f[i-j] 1, f[i]);else f[i] min(f[i-j], f[i]);}}}求答案 int ans INF;rep(i,ph[m],len) {ans min(ans, f[i]);}对s t进行特判 if(s t) { // 特判 s tint cnt 0;rep(i,1,m) if(a[i] % s 0) cnt;coutcnt;return ;}AC代码
const int N 2e5 21;
int a[N], f[N],ph[N];
bool vis[N];
void solve() {int L,s,t,m; cinLstm;rep(i,1,m) cina[i];// 需要进行排序石头位置初始是无序的sort(a1, am1);if(s t) { // 特判 s tint cnt 0;rep(i,1,m) if(a[i] % s 0) cnt;coutcnt;return ;}// 如果 两个石头之间的距离大于等于 s * t进行缩点/*** 因为假设 两个石头距离为 len* 如果 len s * t则在 [s*t, len] 这个区间内的每一个点都可以访问到*/int st s * t;rep(i,1,m) {int dist a[i] - a[i-1];if(dist st) dist st;ph[i] ph[i-1] dist;// 将石头所在的那个点进行赋值为 truevis[ph[i]] 1;}// 因为是大于L就行因此可能有超过L但是是最小次数的情况int len ph[m] st; memset(f, 0x3f, sizeof(f));f[0] 0;rep(i,1,len) {rep(j,s,t) {if(i - j 0) {if(vis[i]) f[i] min(f[i-j] 1, f[i]);else f[i] min(f[i-j], f[i]);}}}int ans INF;rep(i,ph[m],len) {ans min(ans, f[i]);}coutans;
}
