C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 480K, 提交时间: 2020-04-05 22:05:13

#include<bits/stdc++.h>
using namespace std;
long long dp[5010],sumt[5010],sumc[5010];
int main()
{
	int n,s;
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		int t,c;
		scanf("%d%d",&t,&c);
		sumt[i]=sumt[i-1]+t;
		sumc[i]=sumc[i-1]+c;
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<i;j++)
			dp[i]=min(dp[i],dp[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]));
	cout<<dp[n]<<endl;
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 8ms, 内存消耗: 520K, 提交时间: 2022-08-11 21:20:05

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[5555],m[5555];
ll u[5555],n,s;
int main()
{
	cin>>n>>s;
	for(int i=1; i<=n; i++)
	{
		int t,c;
		cin>>t>>c;
		m[i]=m[i-1]+t;
		u[i]=u[i-1]+c;
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1; i<=n; i++)
	for(int j=0; j<i; j++)
	f[i]=min(f[i],f[j]+m[i]*(u[i]-u[j])+s*(u[n]-u[j]));
	cout<<f[n]<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 504K, 提交时间: 2020-10-19 19:39:06

#include<bits/stdc++.h>
using namespace std;
const int nn=5019;
int n,s,t[nn],c[nn],f[nn];
int main(){
	memset(f,0x3f,sizeof f);
	f[0]=0,scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++)
		scanf("%d%d",t+i,c+i),
		t[i]+=t[i-1],c[i]+=c[i-1];
	for(int i=1;i<=n;i++)
		for(int j=0;j<i;j++)
			f[i]=min(f[i],f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]));
	return printf("%d",f[n]),0;
}