海淀区玉泉小学网站 建设方,自治区建设厅官方网站,x wordpress 视差 主题,潍坊网站建设哪家便宜C. Maximum Set
思路#xff1a;
我们求最大数组#xff0c;显然是L一直乘2,直到再乘2就越过区间位置。我们说过#xff0c;再乘一个2就不行#xff0c;那么我们除一个2#xff0c;换句话说#xff0c;就是再乘一个4就不行了。发现#xff0c;我们可能有机会乘一个3
我们求最大数组显然是L一直乘2,直到再乘2就越过区间位置。我们说过再乘一个2就不行那么我们除一个2换句话说就是再乘一个4就不行了。发现我们可能有机会乘一个3234而且我们至多乘一个3。除去一个2必须乘一个数该数小于4并且大于2才能使得除去2后再乘一个数保证数组大小不变所以我们首先求出只由2的倍数组成的最大size然后再求出插入一个3的情况而对于每一组3是可以放在除了第一个数的其他位置上的所以每一组都有size种情况
#include bits/stdc.h
using namespace std;
#define ll long long
const int mod 998244353;int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin t;while (t--){int l, r;cin l r;int k 0;while ((1 k)*l r)k; //k为可以乘的2的个数--k;ll ans (r k) - l 1; //当前ans为可以只乘2获得k1个数的数if (k 0){int cnt (r (k - 1)) / 3 - l 1;//少乘一个2多乘一个3cnt max(0, cnt); //cnt可能小于0ans (ans cnt * k % mod) % mod;}cout k 1 ans endl;}return 0;
}
D. Maximum Subarray
思路
先不考虑修改值x的影响 求n个数字的最大连续子串和因为是连续的。我们可以用dp[i]表示包含i的最大连续子串那么结果就是maxdp[i])。如果我们已经知道dp[i-1],显然dp[i]max( 0,dp[i-1] ) a[i]。dp[i-1]不一定是正数如果是我取你这个连续段不是就不要考虑x后题目要求给整个数组加m个x减去n-m个x。 我们每次更新时都要考虑当前数组加了几个x如果已经加了m个那我们这次就不是a[i]加x而是减x了。如果小于m个那就还是a[i]x。所以我们设dp[i][j]表示包含第i个数字的前i个数字的最大连续子串和其中给前i个数字加了且只加了j个x。那么最大答案就是max(dp[i][j])我们由2.1得出求dp[i][j]是需要分类讨论的 对于dp[i-1][j](即ji时)我们规定了只加j个x那么我们更新时a[i]要减x。所以dp[i][j]max(0,dp[i-1][j])a[i]-x注意我可以不要dp[i-1][j]这段子串和但是我前i-1个还是有j个数字加了x如果继承dp[i-1][j-1]那么我们a[i]x, dp[i][j]max( dp[i][j], max(0, dp[i-1][j-1]) a[i] x)注意题目要求必须加m个x所以我们j不是都从0开始的假如你dp[i][j]更新那么后面还有max(0,m-j)个数字需要加上x那么我们必须保证剩下的n-i个数字够加即jn-im,所以jmax(0,m-ni)jmji
#include bits/stdc.h
using namespace std;
#define ll long long
const int N 2e5 10;ll dp[N][25];
int a[N];int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin t;while (t--){int n, m, x;cin n m x;for (int i 1; i n; i)cin a[i];for (int i 0; i n; i)for (int j 0; j m; j)dp[i][j] 0;ll ans 0;for (int i 1; i n; i)for (int j max(0, m - n i); j m j i; j){if (j i)dp[i][j] max(0ll, dp[i - 1][j]) a[i] - x;//ji就有此更新ji则不用因为前面最多更新j-1个if (j)dp[i][j] max(dp[i][j], max(0ll, dp[i - 1][j - 1]) a[i] x);ans max(ans, dp[i][j]);//答案就是max(dp[i][j]),不是dp[i][m]不要求m个都在我的最大连续子串和范围内更新}cout ans endl;}return 0;
}
