本文共 765 字，大约阅读时间需要 2 分钟。

原题链接：
分类：线性结构
备注：LIS变形

#include<bits/stdc++.h>using namespace std;const int maxn=1e3+5;const int inf=0x3f3f3f3f;int n,s[maxn],dp[maxn];struct Node{       int v,k,c,l;    bool operator < (const Node& rhs) const{           return v<rhs.v;    }}a[maxn];int main(void){       // freopen("in.txt","r",stdin);    while(~scanf("%d",&n)&&n){           for(int i=1;i<=n;i++)            scanf("%d%d%d%d",&a[i].v,&a[i].k,&a[i].c,&a[i].l);        sort(a+1,a+n+1);        memset(dp,inf,sizeof(dp));        dp[0]=0;        for(int i=1;i<=n;i++)            s[i]=a[i].l+s[i-1];        for(int i=1;i<=n;i++){               for(int j=0;j<i;j++){                   dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*a[i].c+a[i].k);            }        }        printf("%d\n",dp[n]);    }    return 0;}