C 解法, 执行用时: 6ms, 内存消耗: 344K, 提交时间: 2022-03-20 16:47:00

#include<stdio.h>
int min(int x,int y){
	int z;
	return z=x<=y?x:y;
}
int main(){
 int sumt[100010],sumc[100010],co[100010];
 int N,S;
 scanf("%d%d",&N,&S);
 sumt[0]=0;
 co[0]=0;
 sumc[0]=0;
 for(int i=1;i<=N;++i){
 	scanf("%d%d",&sumt[i],&sumc[i]);
     sumc[i]+=sumc[i-1];
 	sumt[i]+=sumt[i-1];
 }
  /*for(int i=1;i<=N;++i){
  printf("%d %d ",sumc[i],sumt[i]);
 }*/
    for(int i=1;i<=N;++i)co[i]=1000000000;
 for(int i=1;i<=N;++i){
 	 	for(int j=0;j<i;++j)
 	co[i]=min(co[i],co[j]+sumt[i]*(sumc[i]-sumc[j])+S*(sumc[N]-sumc[j]));

 }
 printf("%d",co[N]);
}

C++(g++ 7.5.0) 解法, 执行用时: 7ms, 内存消耗: 648K, 提交时间: 2023-02-16 17:54:55

#include<iostream>
#include<cstdio>
#include<cstring>
//#include<algorithm>
const int N=50001;
using namespace std;
int main()
{
    int n,s;
    int st[N],sc[N];
    int f[N];
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>st[i]>>sc[i];
        st[i] +=st[i-1];
        sc[i] +=sc[i-1];
        
    }
    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] + (sc[i]-sc[j])*st[i] + s*(sc[n]-sc[j]));
        }
    }
    cout<<f[n];
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 416K, 提交时间: 2020-10-19 19:38:57

#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;
}