网站建设中期检查表怎么写,重庆系统建站怎么用,项目方案计划书,自己有网站怎么做竞价原题链接#xff1a;https://ac.nowcoder.com/acm/contest/74362/E
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format: %lld
题目描述
小红拿到了一个数组#xff0c;她准备选择若干元素…原题链接https://ac.nowcoder.com/acm/contest/74362/E
时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld
题目描述
小红拿到了一个数组她准备选择若干元素乘以 -1使得最终所有元素的和为 0。小红想知道最少需要选择多少个元素
输入描述:
第一行输入一个正整数n代表数组的大小。
第二行输入n个整数ai代表数组的元素。
1≤n≤200
−200≤ai≤200
输出描述:
如果无法使得最终所有元素之和为 0则输出 -1。
否则输出一个整数代表选择元素的最小数量。
示例1
输入
3
1 -2 3
输出
1
说明
选择第一个元素即可。
示例2
输入
3
2 -2 3
输出
-1
解题思路 这个题目要求我们选中数组中的一部分数使得乘以-1然后最终数组和为0要求的是最少要使得多少数乘以-1才能使得最终数组的和为0我之前遇到过一次和这个题目非常相似的题目那个题目是Acwing5386. 进水出水问题这俩个题目很相似所以看到这个题目我很快就想到了解法进水出水问题是将进水总量和出水总量的差值设置为状态这里同样可以这样设置状态我们将没有乘-1和乘了-1的部分的差值设为状态即可由于这里的-200ai200,n200,所以差值可能的范围为[-40000,40000],dp数组会出现负数下标我们需要设置一个偏移量我们可以设置偏移量为40000,那么差的范围变为[0,80000]然后dp处理即可。 dp处理过程 状态定义 操作指的是就某个位置乘以-1这个操作 定义f[i][j]表示处理完前i个物品并且操作部分和没有操作部分差为j的最少操作步数。 设B40000为偏移值 初始化 f[0][0]0,由于要偏移B,所以f[0][B]0 状态转移 当前位置不操作也就是不乘-1; f[i][j]f[i-1][j-a[i]] 当前位置操作也就是乘以-1 f[i][j]f[i-1][ja[i]]1 最终答案 最终答案应该是操作部分和不操作部分差为0所以答案是f[n][0], 由于还有偏移量所以答案是f[n][B] 时间复杂度dp状态个数为O(n*80000),转移为O(1)所以最终时间复杂度为O(80000*n)。 空间复杂度dp数组为O(n*80000)所以空间复杂度为O(80000*n)。 cpp代码如下
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N210,M80010,B40000;int n;
int a[N];
int f[N][M];
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);memset(f,0x3f,sizeof f);f[0][B]0; //初始化for(int i1;in;i)for(int j0;j80000;j){//当前不乘-1操作次数不变if(j-a[i]0)f[i][j]min(f[i][j],f[i-1][j-a[i]]);//当前位置乘-1操作次数加1if(ja[i]80000)f[i][j]min(f[i][j],f[i-1][ja[i]]1);}/*乘-1的个数肯定不会超过数组大小所以当这里的f[n][B]大于n时说明无法使得最终所有元素和为0*/if(f[n][B]n)printf(%d\n,f[n][B]);else printf(%d\n,-1);return 0;
}
