题号：1052
参考题解：
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1052
作者: CoolTeam 更新时间: 2015-08-11 18:26
作者: shutdown 更新时间: 2013-07-30 20:20
作者: VengefulSpirit 更新时间: 2013-06-25 11:17
作者: sb123 更新时间: 2017-08-07 17:58
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include<iostream> #include<algorithm> #include<string> #include<utility> #include<queue> #include<cstdlib> #include<cstring> #include<map> using namespace std; int f[20005]; int Mk[105],M[105]; //ifstream cin("in.txt"); //ofstream cout("out.txt"); int main(){ ios::sync_with_stdio(false); int l, s, t, m,ans=0; cin >> l >> s >> t >> m; for (int i = 1; i <= m; i++){ cin >> Mk[i];//存入M的临时数组 } if (s == t){//当s==t时是特殊情况，只需判断为s/t倍数的点有无石子即可 ；参考CoolTeam。为啥用动态规划过不了，我也不知道 for (int i = 1; i <= m; i++){ if (Mk[i] % s == 0)ans++; } cout << ans; return 0; } //否则需要使用动态规划 memset(f, 0x7f, sizeof(f)); f[0] = 0; sort(Mk + 1, Mk + m + 1); //先给临时数组排个序 for (int i = 1; i <= m; i++){ if (Mk[i] - Mk[i - 1] >= 100)M[i] = M[i - 1] + 100; //如果两相邻石子之间距离大于100，就将他们之间的距离缩小到100 ；参考shutdown的结论，VengefulSpirit的证明过程 else M[i] = M[i - 1] + Mk[i] - Mk[i - 1]; } int M_cnt = 1; for (int i = 1; i <= M[m]+t; i++){ //比较容易的动态规划 ；参考sb123的动规转移方程 for (int j = i-s; j >= max(i - t,0); j--){ f[i] = min(f[j], f[i]); } if (M[M_cnt] == i){ f[i]++; M_cnt++; } } ans = 10000; for (int i = M[m] + t-1; i >= M[m]; i--)ans = min(ans, f[i]); //遍历从最后一个石子到最后一个石子+t-1的最短距离 cout << ans; } |
20180805更新，表示缩点/离散化恶心死了，写了半天60，迫不得已看题解了。、
参考题解：https://www.luogu.org/blog/GXu/solution-p1052
https://peerless.blog.luogu.org/guo-he-xie-ti-bao-gao
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include<iostream> #include<string> #include<algorithm> #include<functional> #define ll long long #define pii pair<int,int> #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int l; int s, t, m; int pos[105]; int d[105]; bool stone[400000]; int f[400000]; int main() { cin >> l >> s >> t >> m; for (int i = 1; i <= m; i++)cin >> pos[i]; sort(pos + 1, pos + m + 1); for (int i = 1; i <= m; i++)d[i] = (pos[i] - pos[i - 1]) % 2520; for (int i = 1; i <= m; i++) { pos[i] = pos[i - 1] + d[i]; stone[pos[i]] = true; } l = pos[m]; for (int i = 1; i <= l + t; i++)f[i] = m; for (int i = 1; i <= l + t; i++) { for (int j = s; j <= t; j++) { if (i >= j)f[i] = min(f[i], f[i - j]); f[i] += stone[i]; } } int ans = m; for (int i = l; i < l + t; i++)ans = min(ans, f[i]); cout << ans; } |