紫书P275: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=105116#problem/A
POJ http://poj.org/problem?id=1260
两个题一种类型：
UVA11400 ： n个灯泡可以选择，每个灯泡有四个属性，v需要电压，k电源费用，c每个灯泡的费用和所需灯泡的数量L，每种类型的灯泡必须配一种类型的电源费用，低电压可以选择换用高电压的灯泡，计算最小费用
首先不能跨电压（1和3, 2），之前一直想不明白，其实可以这么想，1,2,3，电压是递增的，如果1和3在一起，为什么1选择3，不选择2呢？
（1）假设2和3电源费用是相同的，而3的灯泡比2的便宜，所以1选择3会有最小费用，既然如此，2也得选择3才有最优解
（2）假设2和3灯泡的价值是一样的，而3的电源费用比较低，所以1选3，同样，2选3才会有会有最优解
所以不会跨电压！
s[i]表示前i种灯泡的数量，dp[i]前i种灯泡的最小费用，dp[i] = min(dp[j] + (sum[i] - sum[j]) * c[i] + k[i]) 0 <= j < i 表示前j个用最优策略买，后面的以i的价格买
POJ 1260：珍珠的数量a和价格p，每买一种需要多买10个，低等的可以高价买，一样的意思， dp[i] = min(dp[j] + (sum[i]- sum[j] + 10) * p[i])
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = + ;
const int INF = 0x3f3f3f3f;
struct Lamp
{
int v,k,c,l;
};
Lamp lamp[MAX];
int sum[MAX],dp[MAX];
int cmp(Lamp x, Lamp y)
{
return x.v < y.v;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF && n)
{
for(int i = ; i <= n; i++)
{
scanf("%d%d%d%d", &lamp[i].v, &lamp[i].k, &lamp[i].c, &lamp[i].l);
}
sort(lamp + , lamp + n + , cmp);
memset(sum, , sizeof(sum));
memset(dp, , sizeof(dp));
sum[] = lamp[].l;
for(int i = ; i <= n; i++)
sum[i] = sum[i - ] + lamp[i].l;
dp[] = lamp[].c * lamp[].l + lamp[].k;
for(int i = ; i <= n; i++)
{
int minn = INF;
for(int j = ; j < i; j++)
{
minn = min(minn, dp[j] + (sum[i] - sum[j]) * lamp[i].c + lamp[i].k);
}
dp[i] = minn;
}
printf("%d\n", dp[n]);
}
return ;
}
UVA11400
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = + ;
struct Peal
{
int a,p;
};
Peal peal[N];
int c,dp[N],sum[N];
int cmp(Peal x, Peal y)
{
return x.p < y.p;
}
int main()
{
int test;
scanf("%d", &test);
while(test--)
{
scanf("%d", &c);
for(int i = ; i <= c; i++)
{
scanf("%d%d", &peal[i].a, &peal[i].p);
}
//sort(peal + 1, peal + c + 1, cmp); 加排序就WA
memset(sum, , sizeof(sum));
memset(dp, , sizeof(dp));
for(int i = ; i <= c; i++)
{
sum[i] = sum[i - ] + peal[i].a;
}
dp[] = ( peal[].a + ) * peal[].p;
for(int i = ; i <= c; i++)
{
int minn = INF;
for(int j = ; j < i; j++)
{
minn = min(minn, dp[j] + (sum[i] - sum[j] + ) * peal[i].p);
}
dp[i] = minn;
}
printf("%d\n", dp[c]);
}
return ;
}
poj1260