公司网站的制作公司,重庆在线高校开放课程平台,淮北seo,廊坊网站霸屏https://www.lydsy.com/JudgeOnline/problem.php?id1233 数据结构优化dp的代码总是那么抽象 题意#xff1a;奶牛们讨厌黑暗。 为了调整牛棚顶的电灯的亮度#xff0c;Bessie必须建一座干草堆使得她能够爬上去够到灯泡 。一共有N大包的干草#xff08;1N1000001233 数据结构优化dp的代码总是那么抽象 题意奶牛们讨厌黑暗。 为了调整牛棚顶的电灯的亮度Bessie必须建一座干草堆使得她能够爬上去够到灯泡 。一共有N大包的干草1N100000(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个 宽度W_i(1w_i10000)。所有的干草包的厚度和高度都为1. Bessie必须利用所有N包干草来建立起干草堆并且按照他们进牛棚的顺序摆放。她可以相放多少包就放 多少包来建立起tower的地基当然是紧紧的放在一行中。接下来他可以放置下一个草包放在之前一级 的上方来建立新的一级。注意每一级不能比下面的一级宽。她持续的这么放置直到所有的草包都被安 置完成。她必须按顺序堆放按照草包进入牛棚的顺序。说得更清楚一些一旦她将一个草包放在第二级 她不能将接下来的草包放在地基上。 Bessie的目标是建立起最高的草包堆。 Input 第1行一个单一的整数N。 第2~N1行一个单一的整数:W_i。 奥妙重重dp题。 第一眼觉得是个反向贪心从上往下取每次取最小的可以形成下一层的干草集合后来发现是个假算法。 反例 6 6 2 3 7 10 11 既然贪心不行,就自然而然想到dp考虑dp[i]表示到这一层的最大层数发现不可行因为这样的dp方法不能固定一个状态。 但是这一题有一个很强的证明对于一座干草堆而言基底最小的状态一定为最优状态。 也就是说每一个状态中地基最小的状态就是高度最高的状态我们可以简单的推断一下每一个高度最高的状态必然可以从下往上贪心的堆干草最终达到基底最小的状态。 这样我们原来的dp就变成了dp[i]表示i -- n种所有干草组成的集合形成的最小的干草堆的基底。 我们反向从N - 1遍历对于i需要找到一个最小的大于i的j满足 sum[j - 1] - sum[i - 1] dp[j] 这样就变成了一个O(N * N)的dp但是这还不够到这一步需要考虑优化。 我们将转移方程变形 变成sum[i - 1] sum[j - 1] - dp[j]注意到我们每次需要的考虑的集合在每一次询问i的时候都多加入1个以及当存在k j sum[k - 1] - dp[k] sum[j - 1] - dp[j]的时候j就是一个多余的状态sum[i - 1]由于其前缀和的性质事实上是递减的对于每一次集合内的查找我们在查找到最小的j的时候可以将其余的比sum[i - 1]大的状态全部舍弃。 以上三个性质中显然可以发现用来维护这个集合的数据结构就是单调队列最终时间复杂度O(n) #include map
#include set
#include ctime
#include cmath
#include queue
#include stack
#include vector
#include string
#include cstdio
#include cstdlib
#include cstring
#include sstream
#include iostream
#include algorithm
#include functional
using namespace std;
#define For(i, x, y) for(int ix;iy;i)
#define _For(i, x, y) for(int ix;iy;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf(%d, x)
#define Sca2(x,y) scanf(%d%d,x,y)
#define Scl(x) scanf(%lld,x);
#define Pri(x) printf(%d\n, x)
#define Prl(x) printf(%lld\n,x);
#define CLR(u) for(int i0;iN;i)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pairint,int
#define PIL pairint,long long
#define PLL pairlong long,long long
#define pb push_back
#define fi first
#define se second
typedef vectorint VI;
const double eps 1e-9;
const int maxn 1e5 10;
const int INF 0x3f3f3f3f;
const int mod 1e9 7;
int N,M,tmp,K;
int a[maxn];
int sum[maxn];
int dp[maxn];
int f[maxn];
int Queue[maxn];
int main()
{int N; Sca(N); //sum[i - 1] sum[j - 1] - dp[j]For(i,1,N){Sca(a[i]);sum[i] sum[i - 1] a[i];} int head 1,tail 1; Queue[1] N 1;_For(i,N,1){while(head tail sum[i - 1] sum[Queue[head 1] - 1] - dp[Queue[head 1]]) head;dp[i] sum[Queue[head] - 1] - sum[i - 1];f[i] f[Queue[head]] 1;while(head tail sum[i - 1] - dp[i] sum[Queue[tail] - 1] - dp[Queue[tail]]) tail--;Queue[tail] i;}printf(%d,f[1]);#ifdef VSCodesystem(pause);#endifreturn 0;
} 转载于:https://www.cnblogs.com/Hugh-Locke/p/9671948.html
