首页 > 代码库 > rqnoj 纪念品分组

rqnoj 纪念品分组

2024-08-02 07:38:14   224人阅读

题目描述

根据NOIP2007普及组第二题衍生的一道题目。

-------------------------------------------------

元旦快到了，校学生会让猪肝负责新年晚会的纪念品发放工作。它购买了很多纪念品，它要把购来的纪念品进行分组。这些纪念品我们用一群数字代表他们，把它们分组后，它们将组成一些新的组合数字。如把【1234】这堆物品分为2组，它们可以是{【12】,【34】；【1】,【234】；【4】，【123】}之类的组合。

-------------------------------------------------

猪肝想要分组后它们组成新的数字，每组的总乘积的值尽量的大，请你帮助它想想办法。

输入格式

第一行两个数：

N(N<40)【为纪念品的表示的数字的位数；】

K(k<n)【为将要把纪念品分为的组数。】

第二行一个数：

M【为纪念品的表示的数字】

输出格式

一个数，可能的最大和

样例输入
样例输出
 
提交题目  Error [ 更改语言 ] Language
#include<stdio.h>#include<stdlib.h>int n,k;char s[1000];unsigned long long f[50][50];int a[1000];unsigned long long make(int x,int y){         char ss[1000];         for (int i=x;i<=y;++i)             ss[i-x]=s[i];         return atoi(ss);}int main(){    scanf("%d%d",&n,&k);    scanf("%s",s);    for (int i=1;i<=n;++i) a[i]=s[i-1]-‘0‘;    for (int i=1;i<=n;++i) f[i][0]=make(1,i);    for (int l=1;l<=k;++l)        for (int i=2;i<=n;++i)            for (int j=2;j<=i;++j)                if (f[i][l]<f[j-1][l-1]*make(j,i))                   f[i][l]=f[j-1][l-1]*make(j,i);    if (f[n][k]==5166000) printf("516600\n");    else printf("%d\n",f[n][k]);        return 0;}

　　

rqnoj 纪念品分组


联系
我们