为某网站做网站推广策划方案,用别的域名给网站做竞价,网站的建设外链优化,建设部网站怎么查岗位人员大家好#xff0c;欢迎来到codeforces专题。今天选择的问题是1443场次的D题#xff0c;这题是全场倒数第三题#xff0c;截止到现在一共通过了2800余人。这题的思路不算难#xff0c;但是思考过程非常有趣#xff0c;这也是这一期选择它的原因。链接#xff1a;https://c…大家好欢迎来到codeforces专题。今天选择的问题是1443场次的D题这题是全场倒数第三题截止到现在一共通过了2800余人。这题的思路不算难但是思考过程非常有趣这也是这一期选择它的原因。链接https://codeforces.com/contest/1443废话就先说到这里下面我们就来看题吧。题意给定n个整数对于这n个整数我们可以采取两种操作。第一种操作是在数组左侧选择连续的k个整数减1第二种操作是选择右侧的连续k个整数减1。比如假设数组是[3, 2, 2, 1, 4]比如我们选择k2取最左侧进行操作那么我们会得到[2, 1, 2, 1, 4]。如果我们选择k3再取右侧进行操作可以得到[2, 1, 1, 0, 3]。现在我们想要知道给定这样的数组我们能否通过这两个操作将数组清空。如果可以输出YES否则的话输出NO。样例首先输入一个整数t表示测试数据组数。对于每组测试数据首先输入一个整数n表示数组当中元素的个数。之后输入一行整数。可以保证每一组测试数据的n之和不会超过30000.题解由于我们对于k没有限制最多我们可以一次对数组内的n个元素全部减一。所以k不是限制我们的因素最大的限制其实是在元素本身。我们分析一下会发现由于数组当中的元素大小不一这其实是隐形的限制。举个例子比如[2, 8, 3]。由于我们只能从两侧开始选择元素进行操作所以由于2和3比较小会导致我们没有办法把中间的8消除完。当然无法消除的原因可能有好几种但基本上都是由于元素的大小不一导致的。首先我们对这个问题进行一个简单的建模题目当中没有限制执行的次数所以减一次和减很多次是一样的。我们可以把可以合并的操作合并在一起理解成执行一次可以减去任意的值。并且我们可以把操作反向理解把数组当中的值看成是容器这样我们从数组当中减去值的操作就可以等价理解成向容器当中输入水流这样会容易理解一些。我的第一想法很简单我们可以求出每个位置能够从左侧和右侧分别获得的最大数值。只要左右两侧能够获取的流量之和大于等于容器的容积那么就说明我们可以获取到足够的流量灌满所有的容器。我很快就写出了代码建了一个二维数组dp[i][0]表示第i个元素从左侧源头能够获取的最大流量。dp[i][1]表示第i个元素可以从右侧源头获取到的最大流量。由于我们需要保证每个容器存储的体积不能超过容量所以我们需要很容易得出递推关系。dp[i][0] min(dp[i-1][0], a[i]) 关系明确了很容易写出代码using namespace std;int a[30006], dp[30006][2];int main() {int t, n;scanf(%d, t);rep(z, 0, t) {scanf(%d, n);rep(i, 1, n1) scanf(%d, a[i]);MEM(dp, 0x3f);// 从左侧递推获取dp[i][0]rep(i, 1, n1) {dp[i][0] min(dp[i-1][0], a[i]);}// 从右侧递推获取dp[i][1]Rep(i, n, 0) {dp[i][1] min(dp[i1][1], a[i]);}bool flag 1;rep(i, 1, n1) {// 如果存在某个元素从左右两侧获取的流量之和无法灌满// 则返回NOif (dp[i][0] dp[i][1] a[i]) {flag 0;break;}}puts(flag ? YES : NO);}return 0;
}
但是很遗憾这样不能AC因为dp的数组维护的其实是某个位置从左侧和从右侧能够获取的最大值这是一个理想情况很有可能这个理想情况是无法实现的。举个很简单的反例[2, 4, 2, 4, 2]这些元素左右两边能够获取到的最大流量值都是2但是这里是有问题的。观察一下会发现数组当中的两个4是无法同时满足的无法满足的原因是因为中间的2限制了通过的流量。虽然理论上从左往右和从右往左能够通过的流量上限都是2但是这个上限是无法同时取到的。这个问题用上述的方法是解决不了的所以需要重新构思。这里我们深入分析会发现一个比较麻烦的点在于每个点都有两个源头我们无法确定流量分配。不过这个问题也很好解决因为左右两边的流量是没有区别的。所以我们可以以某一侧为主剩余不够的流量再由另一侧补充。比如我们可以以左侧为主把左侧能够获取的流量开启到最大不够地再通过右侧补充。如果右侧的流量无法补充那么就说明无解。我们用dp[i][0]记录i位置从左侧获取的流量dp[i][1]记录i位置从右侧获取的流量。#include iostream
#include cstdio
#include cstring
#include queue
#include vector
#include cmath
#include cstdlib
#include string
#include map
#include set
#include algorithm
#include time.h
#include functional
#define rep(i,a,b) for (int ia;ib;i)
#define Rep(i,a,b) for (int ia;ib;i--)
#define foreach(e,x) for (__typeof(x.begin()) ex.begin();e!x.end();e)
#define mid ((lr)1)
#define lson (k1)
#define rson (k1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N1000050;
const long long Mod1000000007;using namespace std;int a[30006], dp[30006][2], min_need[30006][2], record[30006][2];int main() {int t, n;scanf(%d, t);rep(z, 0, t) {scanf(%d, n);rep(i, 1, n1) scanf(%d, a[i]);MEM(dp, 0x3f);dp[0][1] 0;bool flag 1;rep(i, 1, n1) {# 如果右侧需要的流量大于容器容积if (dp[i-1][1] a[i]) {flag 0;break;}# 左侧能够获取的流量因为i-1从右侧获取的流量也会经过i所以需要减去dp[i][0] min(dp[i-1][0], a[i] - dp[i-1][1]);# 需要从右侧获取的流量需要累加dp[i][1] dp[i-1][1] max(0, a[i] - dp[i][0] - dp[i-1][1]);}puts(flag ? YES : NO);}return 0;
}
虽然这个是很简单的动态规划的思想但是一些细节很容易忽略。比如说i-1位置的右侧流量会流经i以及大于i每一个位置。所以每一个位置的右侧流量是累加的是越来越大的。只要能够把握住这点AC是不难的。总体来说这题的难度不大对于思维的要求不是很高但是非常考验思维的缜密性和逻辑性。非常适合用来进行思维锻炼。今天的文章就到这里衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话请来一个三连支持吧~点赞、关注、转发原文链接求个关注原创 | codeforces 1443D解法简单思维缜密的动态规划问题mp.weixin.qq.com
