题目大意：有一个照明系统需要用到n种灯，每种灯的电压为V，电源费用K，每个灯泡费用为C，需要该灯的数量为L。注意到，电压相同的灯泡只需要共享一个对应的电源即可，还有电压低的灯泡可以被电压高的灯泡替代。为了节约成本，你将设计一种系统，使之最便宜。
分析：首先需要明确一种灯泡要么全部换，要么不换。如果换一部分的话，首先电源费用得不到节约，那么节约的部分就只来自于换的那部分灯泡，既然可以节约钱干嘛不干脆全部换了呢?
明确了这点之后
我们应该对决策进行一定的限制: 求前i个灯泡的最小花费时，只允许用第i种灯泡进行替换! 如何替换呢？ 只能替换1 到i 中序号连续的灯泡！！！ 即决策应为选择一个j，替换掉序号为 j 到i - 1的所有灯泡，使得前i号灯泡花费最小。那么最终 dp[n]即为答案。
d[i]为只考虑前i种灯泡的最小花费，状态转移方程：d[i] = min{d[i] + (s[i] - s[j]) * c[i] + k[i]} 其中s[i]为前i种灯泡的总数量。 但这样做是否正确呢，首先上面的方法在求前i 个灯泡的最小花费时，只能用第i个灯泡替换，这样并不影响，因为通过循环所有的灯泡都会用来替换。 问题关键是只考虑替换连续区间的灯泡造成解丢失的情况。比如说会不会出现最优解是序号为1， 3的灯泡被一种灯泡替换，序号为2的被另一种替换或不被替换。 假设这种情况下是最小花费，那么替换序号2的灯泡的单价一定小于替换序号1的灯泡的单价，否则不会是最小值，既然替换序号2的灯泡的单价小于替换序号1的灯泡的单价，那么用替换2的灯泡去替换灯泡1，就会产生更小的花费，这与假设向矛盾，所以假设不成立，即前面的决策不会漏掉答案。 #include #define ll long long #define pb push_back #define inf 0x3f3f3f3f #define pll pair #define rep(i,a,b) for(int i=a;i<=b;i++) #define rep1(i,a,b) for(int i=a;i>=b;i--) #define rson rt<<1|1,m+1,r #define lson rt<<1,l,m using namespace std; const int N=1e3+100; ll dp[N],s[N]; struct node { ll v,k,c,l; }app[N]; bool cmp(node a,node b) { return a.vint main() { ios::sync_with_stdio(false ); int n; while(cin>>n&&n) { rep(i,1,n) cin>>app[i].v>>app[i].k>>app[i].c>>app[i].l; sort(app+1,app+1+n,cmp); rep(i,1,n) s[i]=s[i-1]+app[i].l; rep(i,1,n) { dp[i]=app[i].k+app[i].c*s[i]; rep(j,0,i-1) dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*app[i].c+app[i].k); } cout<return 0; }