求助这样写状态转移方程为什么不对
查看原帖
求助这样写状态转移方程为什么不对
130819
Hayzeros楼主2022/9/28 17:07

p2365

#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
const int maxn=3e5+5;
int f[maxn],t[maxn],ta,c,sumt[maxn],sumc[maxn];
int min(int a,int b){return a<b? a:b;}
signed main()
{
    int n,s;
    scanf("%lld%lld",&n,&s);
    memset(f,0x7f,sizeof(f));
    f[0]=0;
    for (int i=1; i<=n; i++) scanf("%lld%lld",&ta,&c),sumt[i]=sumt[i-1]+ta,sumc[i]=sumc[i-1]+c;
    for (int i=1; i<=n; i++)
    {
        int k=(int)1<<62;
        for (int j=0; j<i; j++)
        {
            k=min(k,f[j]+(t[j]+s+sumt[i]-sumt[j])*(sumc[i]-sumc[j]));  //t[j]表示f[j]方案用时
            if (k<f[i]) f[i]=k,t[i]=t[j]+s+sumt[i]-sumt[j];
        }
    }
    printf("%lld",f[n]);
    return 0;
}
2022/9/28 17:07
加载中...