P 1018積算最大(ダイナミックプランニング+高精度)
1922 ワード
P 1018積算最大(ダイナミックプランニング+高精度)
タイトルの説明
今年は国際数学連盟が確定した「2000――世界数学年」であり、わが国の有名な数学者華羅庚氏の生誕9090周年にもふさわしい.華羅庚さんの故郷江蘇金壇で、ユニークな数学知能コンテストの活動を組織し、あなたの親友XZXZも参加することができました.イベントでは、司会者がイベントに参加したすべての選手にこのようなテーマを出しました.
長さNNの数字列が設けられており、KK個の乗号を用いてK+1 K+1個の部分に分割することを選手に要求し、このK+1 K+1個の部分の積を最大にすることができるように分法を見つけた.
また、司会者は選手が問題の意味を正しく理解できるようにするために、次のような例を挙げた.
数字の列があります:312312、N=3、K=1 N=3、K=1の時以下の2種類の分法があります:
1、 3\times 12=363×12=362、 31\times 2=6231×2=62
このとき,タイトル要求に合致した結果は,31times 2=6231であった.×2=62
今、あなたの良い友达XZXZを助けてプログラムを設計して、正しい答えを求めてください.
にゅうしゅつりょくけいしき
入力形式:
プログラムの入力は2行あります.
第1行は22個の自然数N,KN,K(6≦N≦40,1≦K≦66≦N≦40,1≦K≦6)を有する.
2行目は長さNNの数字列です.
出力フォーマット:
結果は画面に表示され、入力に対して求めた最大積(自然数)が出力されます.
入出力サンプル
入力サンプル#1:コピー
出力サンプル#1:コピー
説明
NOIp 2000向上グループ第二題
タイトルの説明
今年は国際数学連盟が確定した「2000――世界数学年」であり、わが国の有名な数学者華羅庚氏の生誕9090周年にもふさわしい.華羅庚さんの故郷江蘇金壇で、ユニークな数学知能コンテストの活動を組織し、あなたの親友XZXZも参加することができました.イベントでは、司会者がイベントに参加したすべての選手にこのようなテーマを出しました.
長さNNの数字列が設けられており、KK個の乗号を用いてK+1 K+1個の部分に分割することを選手に要求し、このK+1 K+1個の部分の積を最大にすることができるように分法を見つけた.
また、司会者は選手が問題の意味を正しく理解できるようにするために、次のような例を挙げた.
数字の列があります:312312、N=3、K=1 N=3、K=1の時以下の2種類の分法があります:
1、 3\times 12=363×12=362、 31\times 2=6231×2=62
このとき,タイトル要求に合致した結果は,31times 2=6231であった.×2=62
今、あなたの良い友达XZXZを助けてプログラムを設計して、正しい答えを求めてください.
にゅうしゅつりょくけいしき
入力形式:
プログラムの入力は2行あります.
第1行は22個の自然数N,KN,K(6≦N≦40,1≦K≦66≦N≦40,1≦K≦6)を有する.
2行目は長さNNの数字列です.
出力フォーマット:
結果は画面に表示され、入力に対して求めた最大積(自然数)が出力されます.
入出力サンプル
入力サンプル#1:コピー
4 2
1231
出力サンプル#1:コピー
62
説明
NOIp 2000向上グループ第二題
#include
#include
#include
using namespace std;
long long dp[45][60]; // :dp[i][j] i j
string str; // :
int n,k;//n k
long long integer[45];
long long cut(int left,int right)
{
int i;
long long product=0;
long long d=1;
for(i=right;i>=left;i--)
{
product+=integer[i]*d;
d*=10;
}
return product;
}
int main()
{
int i;
int a,b;
scanf("%d%d",&n,&k);
cin>>str;
for(i=1;i<=n;i++)
integer[i]=str[i-1]-'0';
for(i=1;i<=n;i++)
dp[i][0]=cut(1,i); //
for(i=2;i<=n;i++) // i
{ // , i 2
for(a=1;a<=min(i-1,k);a++) //
{ // , , , i 1 。0
for(b=a;b