[USACO 2009 Ope G]Tower of Hay

C++14(g++5.4) 解法, 执行用时: 53ms, 内存消耗: 1636K, 提交时间: 2019-08-13 08:38:07

#include<iostream>
#include<cstdio>
#include<algorithm>
#define FOR(i,a,b) for(register int i(a);i<=b;++i)
#define ROF(i,a,b) for(register int i(a);i>=b;--i)
using namespace std;
const int N(1000010);
int n;
int f[N],g[N],sum[N];
int main()
{
    cin>>n;ROF(i,n,1)cin>>sum[i];
    FOR(i,1,n)sum[i]+=sum[i-1];
    FOR(i,1,n)
    {
        ROF(j,i-1,0)
        if(sum[i]-sum[j]>=g[j])
        {
            f[i]=f[j]+1;
            g[i]=sum[i]-sum[j];
            break;
        }
    }
    cout<<f[n]<<'\n';
    return 0;
}

Pascal(fpc 3.0.2) 解法, 执行用时: 49ms, 内存消耗: 1896K, 提交时间: 2019-08-12 14:30:41

var
n,i,j:longint;
a,f,g:array[0..1000010]of longint; 
begin
 read(n);
 for i:=n downto 1 do read(a[i]);
 for i:=1 to n do a[i]:=a[i]+a[i-1];
 for i:=1 to n do
  begin
   for j:=i-1 downto 0 do
    if a[i]-a[j]>=g[j] then begin
                             f[i]:=f[j]+1;
                             g[i]:=a[i]-a[j];
                             break;
                            end;
  end;
 writeln(f[n]);
end.

C++ 解法, 执行用时: 35ms, 内存消耗: 2296K, 提交时间: 2022-04-30 21:16:39

#include<bits/stdc++.h>
#define w while
#define f(l,r) for(int i=l;i<=r;i++)
#define r(r,l) for(int i=r;i>=l;i--)
using namespace std;
int n,a[100001],s[100001],f[100001],g[100001],q[100001],l,r;
int main() {
	cin>>n;
	r(n,1)cin>>a[i];
	f(1,n)s[i]=s[i-1]+a[i];
	f(1,n){w(l<r&&s[q[l+1]]+g[q[l+1]]<=s[i])l++;f[i]=f[q[l]]+1;g[i]=s[i]-s[q[l]];w(l<r&&s[q[r]]+g[q[r]]>=s[i]+g[i])r--;q[++r]=i;}
	cout<<f[n];
	return 0;
}

详情