C++(clang++ 11.0.1) 解法, 执行用时: 191ms, 内存消耗: 660K, 提交时间: 2022-09-19 18:00:53

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int N = 2e4 + 5 ;
const ll INF = 1ll<<60 ;
int n,c ;
int p[N],s[N] ;
ll f[2][N] ;
int main()
{
	cin>>n>>c ;
	for(int i=1;i<=n;++i) cin>>p[i] ;
	for(int i=1;i<=n;++i) cin>>s[i] ;
	for(int i=1;i<=n;++i) f[0][i]=INF ;
	f[0][0]=0 ;
	ll ans=INF ;
	for(int i=1;i<=n;++i)
	{
		int now=i&1,pre=now^1 ;
		for(int j=0;j<=n;j++) f[now][j]=INF ;
		for(int j=0;j<=i;j++)
		{
			if(j<i) f[now][j]=min(f[now][j],f[pre][j]+s[i]) ;
			if(j>0) f[now][j]=min(f[now][j],f[pre][j-1]+p[i]+((ll)i-j)*c) ;
		}
	}
	for(int i=0;i<=n;++i) ans=min(ans,f[n&1][i]) ;
	cout<<ans<<'\n' ;
	return 0 ;
}

C++(g++ 7.5.0) 解法, 执行用时: 12ms, 内存消耗: 556K, 提交时间: 2022-09-27 16:42:01

#include <iostream>
#include <algorithm>

using namespace std;

using i64 = long long;

const int N = 10010;

int n, c;
int s[N], t[N];
i64 val[N];

int main() {
    cin >> n >> c;
    i64 res = 0;
    for (int i = 1; i <= n; i++) cin >> s[i], res += s[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) val[i] = 1ll * (n - i) * c + t[i] - s[i];
    sort(val + 1, val + n + 1);
    i64 ans = 1e18;
    for (int i = 1; i <= n; i++) {
        res += val[i] - 1ll * (i - 1) * c;
        ans = min(ans, res);
    }
    cout << ans << '\n';
    return 0;
}