Print Words in Lines(台湾亚洲区预选赛第一题)
题目的位置:http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=as1&year=2006
#include <iostream.h>
#include <math.h>
#include <stdio.h>
#include <malloc.h>
#define COUNT 20
#define MAX_NUM 14
//数组顺序保存一句话的每个单词字符数
int * words=NULL;
int words_number; //单词数
int Mcount;//最大的字符数
void InitWords(/*int * &wordss*/)
{
int *wordss=NULL;
printf("请输入限制数\n");
scanf("%d",&Mcount);
printf("请输入单词数目\n");
scanf("%d",&words_number);
wordss=(int *)malloc(words_number*sizeof(int));
printf("下面输入每个单词的数值\n");
for(int i=0;i<words_number;i++)
{
printf("输入第%d个数\t",i);
scanf("%d",&wordss[i]);
}
words=wordss;
}
//int words[14]={4,2,1,4,2,8,5,3,3,7,4,3,3,10};
//----------------------------------------
int j=0;
//double penalty;//惩罚值
double s=0;
double penaltyfun(int j)
{
if(j>words_number-1)
return 0;
double min=0X7FFFFFFF;
int i=j;//i最初指向words[]初值
int len=words[i];
int len_s=len;
double penalty(0);
while(len<Mcount&&i<words_number)
{
if(len_s<Mcount)//less than COUNT,count penalty
penalty=pow((Mcount-len_s),2);
else
penalty=0;
penalty+=penaltyfun(++i);
if(penalty<min)
min=penalty;
//min+=
//i++;
len+=words[i];
//len_s+=words[i]+1;
//len_s=len+i-j;//加上了空格
len_s++;//加空格
len_s+=words[i];//加上所加的新单词的字符数
}
return min;
}
void main()
{
InitWords();
cout<<penaltyfun(0)<<endl;
}
评论
发表评论