首页 > 不平衡数组
开通博客写题解
头像 sunsetcolors
发表于 2020-06-05 22:00:43
C 不平衡数组 题目地址： https://ac.nowcoder.com/acm/contest/5881/C 基本思路: 因为每一位只能加一次，所以比较容易想到，用表示当前位置不加一，表示当前位置加一，那么我们每次只要关心前后两位在加一或不加的状态下会不会冲突就行了，不冲突我们就能递推了 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 cheeserish
发表于 2020-06-06 21:04:14
表示，dp的魅力；只要知道这题用dp做，就差不多了；怎么想到dp？一方面做题多，另一方面排除法，别的都不行。这道题求最小值，最值一般dp。二分，贪心。最后选dp；dp[][0/1]表示，到达i的时候，前i-1个数满足题意，第i个数是否需要+/-1；需要判断a[i]与a[i-1]的关系； #inclu 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Eihuvita.
发表于 2020-06-07 00:01:48
题意 给定一个长度为 n 的数组。要求相临的数大小不相同，假如相临数的相同，你可以通过将 a[i]+1 来改变它的大小，但是需要付出 b[i]的代价，同时对于每个 a[i]只能加一次。问你付出的最小代价。 输入描述 第 1 行 1 个整数 n，表示数组长度为 n接下来 n 行，每行 2 个正整 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”