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;


}

评论

此博客中的热门博文

Linux/ARM Page Table Entry 属性设置分析

由RFE指令引发的一串故事

提交了30次才AC ---【附】POJ 2488解题报告