魔站网站开发,模仿网站建设,网站开发是什,杭州钱塘区网站建设CF1497E2 Square-free division (hard version)
题意#xff1a;
数组 a 由 n 个正整数构成。你需要将它们分割成最小数量的连续子段#xff0c;使得每一个子段中的任意两个数#xff08;不同位置#xff09;的乘积不为完全平方数。 除此之外#xff0c;你被允许在分割之…CF1497E2 Square-free division (hard version)
题意
数组 a 由 n 个正整数构成。你需要将它们分割成最小数量的连续子段使得每一个子段中的任意两个数不同位置的乘积不为完全平方数。 除此之外你被允许在分割之前进行最多 k 次修改操作。 在一次修改操作中你可以选择数组中的某个位置的数将该位置的数变为任意正整数。 请问连续子段的最小数量是多少在最多 k 次操作后
题解
本题多了修改操作一开始部分和E1情况一样还是先对数组a[]a[]a[]进行操作将偶数质因子去掉奇数质因子留下一个。 很明显要dp转移如何转移 先设dp[i][j]表示前i个数字修改了j的连续字段的最小数量 怎么转移呢 单单考虑第i个是否修改貌似是不够的一个思想是上一次划分到k修改次数为p则从dp[k][p]转移到dp[i][j]。对于[k1,i]这一段如果这一段的最小需要改变数量为num那么就有pnumj。 这样我们就需要知道任意一段[l,r]的最小修改次数 我们设l[i][k]:表示最小的pos使得[pos,i]作为一个整段时消耗了x从修改为什么要这样设这样可以极大的简化dp过程,对于一个k不同的i,我们可以快速找到上一个状态j从状态j转移到当前的状态i 转移方程dp[i][j]moin(dp[i][j],dp[l[i][x]][j−x]1)dp[i][j]moin(dp[i][j],dp[l[i][x]][j-x]1)dp[i][j]moin(dp[i][j],dp[l[i][x]][j−x]1) 对于数组l[i][k]j对于一个确定的k当i增加时结果j必然单调不减,所以j我们可以利用双指针O(n)求这样求l[][]数组的复杂度是O(nk) dp复杂度是O(nk2)O(nk^2)O(nk2)
代码
// Problem: E2. Square-free division (hard version)
// Contest: Codeforces Round #708 (Div. 2)
// URL: https://codeforces.com/contest/{getProblemIndexes(problemCurrentPageList[i][0])[0]}/problem/E2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e5 9;
int dp[maxn][30];
int l[maxn][30];
int vis[20000020];
int a[maxn];
int main()
{//rd_test();int t;read(t);while (t--) {int n, k;read(n, k);for (int i 1; i n; i) {read(a[i]);int now a[i];for (int j 2; j * j now; j) {int cnt 0;while (now % j 0) {now/ j;cnt;}for (int k 1; k cnt; k)a[i]/ j;if (cnt % 2 1)a[i]* j;}}for (int lim 0; lim k; lim) {int cnt 0;for (int i 1, j 1; i n; i) {vis[a[i]];if (vis[a[i]] 2)cnt;if (cnt lim) {while (cnt lim) {if (vis[a[j]] 2)cnt--;vis[a[j]]--;j;}}l[i][lim] j;}for (int i 1; i n; i)vis[a[i]] 0;}for (int i 0; i n; i)for (int j 0; j k; j)dp[i][j] INF_int;dp[0][0] 0;for (int i 1; i n; i) {for (int j 0; j k; j) {for (int x 0; x j; x) {dp[i][j] min(dp[i][j], dp[l[i][x] - 1][j - x] 1);}}}int ans INF_int;for (int i 0; i k; i) {ans min(ans, dp[n][i]);}cout ans endl;}return 0;//Time_test();
}
