返回信息流[ 用户 ppooooll 在转载时对文章内容进行了编辑 ]
题目链接：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1260
按照前人的解题思路写的程序，过了测试用例，还是各种wa。。。弄了有8个小时了，把我这个新手的求知欲消耗殆尽，只想ac了得了。。。谁能帮我看看代码哪错了。。。。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n_case, n, p[201], temp_price, total_amount;
struct pearl{
int amount;
int price;
};
pearl pl[201];
/*int cmp(const void *a, const void *b){
return(*(pearl *)a).price > (*(pearl *)b).price ? 1 : -1;
}
*/
int main(){
scanf("%d", &n_case);
while(n_case--){
scanf("%d", &n);
for(int i=0;i<n;i++){
scanf("%d %d", &pl[i].amount, &pl[i].price);
}
// qsort(pl, n, sizeof(pl[0]), cmp);
p[0] = 0;
p[1] = pl[0].price * (pl[0].amount + 10);
for(int i=2; i<n+1; i++){
total_amount = 10;
p[i] = 10000000;
for(int j=i; j>0; j--){
total_amount += pl[j-1].amount;
temp_price = pl[i-1].price * total_amount + p[j-1];
if(temp_price < p[i])p[i] = temp_price;
}
}
printf("%d\n", p[n]);
}
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / henan / #199951同步于 2009/12/13
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Henan机器人发帖
冬总帮我查异常
ppooooll
2009/12/13镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
就是要是买每一种珍珠的话，要多交10个珍珠的起步价
所以有时候买贵的少种类的珍珠比便宜的多种类的珍珠更划算
1.如果将第i种珍珠替换为第i＋k种珍珠，要么全部替换，要么不替换。2.对于某一高档次珍珠i，若要和低档次的珍珠合并，那么这些低档次的珍珠必须是和它紧邻的，也就是说，它只有和第i－1，i―2，…，i－k类珍珠合并，同时这种合并必须是连续的.
建立动态规划数组res[]，其中res[i]表示当有i种珍珠是所需要的最小费用。于是，我们有：
res[i] =min ( res[k] +(a[k+1]+a[k+2]+...+a[i]+10) ×P[i])，k=1,….i-1;
最后res[c]中的内容即是结果。
思路就这样了，冬总快发威
【 在 BismarckDD (豫韵悠悠|以仁为本|〖冰雪猪联盟〗|盟众) 的大作中提到: 】
: 这个等我慢慢看看。。。我看了一会还是一头雾水啊。。。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<iostream>
using namespace std;
int n_case, n, p[201], temp_price, total_amount;
struct pearl
{
int amount;
int price;
};
pearl pl[201];
/*int cmp(const void *a, const void *b)
{
return(*(pearl *)a).price > (*(pearl *)b).price ? 1 : -1;
} */
int main()
{
scanf("%d", &n_case);
while(n_case--)
{
scanf("%d", &n);
for(int i=0;i<n;i++)
{
scanf("%d %d", &pl[i].amount, &pl[i].price);
}
//qsort(pl, n, sizeof(pearl), cmp);
p[0] = 0;
p[1] = pl[0].price * (pl[0].amount + 10);
for(int i=2; i<n+1; i++)
{
total_amount = 10;
p[i] = INT_MAX;
for(int j=i; j>0; j--)
{
total_amount += pl[j-1].amount;
temp_price = pl[i-1].price * total_amount + p[j-1];
if(temp_price < p[i]) p[i] = temp_price;
}
}
printf("%d\n", p[n]);
}
system("pause");
return 0;
}
我怀疑是p[i]的预设置值太小了。。。换成int_MAX就过了
【 在 ppooooll (\_/-->\________/) 的大作中提到: 】
: 就是要是买每一种珍珠的话，要多交10个珍珠的起步价
: 所以有时候买贵的少种类的珍珠比便宜的多种类的珍珠更划算
: 1.如果将第i种珍珠替换为第i＋k种珍珠，要么全部替换，要么不替换。2.对于某一高档次珍珠i，若要和低档次的珍珠合并，那么这些低档次的珍珠必须是和它紧邻的，也就是说，它只有和第i－1，i―2，…，i－k类珍珠合并，同时这种合并必须是连续的.
: ...................