codevs.cn 1017 乘积最大

2017-01-06 07:57:41来源:CSDN作者:ChorolopLanceloat人点击

第七城市

感觉写的时候还是思考的偏多一点,多次测试后一次AC,这里用到了一个矩阵,主要问题是各元素之间的关系,也就是那个奇葩状态转移方程,,,


#include<cstdio>

#include<iostream>

using namespace std;


long long field[50][15];

int num[50];


long long GET(int begin,int end)

{

long long final = 0;

for(int i = begin;i <= end;i++)

{

final = final * 10 + num[i];

}

return final;

}


void PUT()

{

for(int i = 0;i < 50;i++)

{

for(int j = 0;j < 6;j++)

{

printf("%-5d ",field[i][j]);

}

printf("/n");

}

return ;

}


int main()

{

int n,k,temp;

scanf("%d %d",&n,&k);

for(int i = 0;i < n;i++)

{

scanf("%1d",&num[i]);

}

field[0][0] = num[0];

for(int i = 1;i < n;i++)

{

field[i][0] = field[i-1][0] * 10 + num[i];

}

for(int kk = 1;kk <= k;kk++)

{

field[kk][kk] = field[kk-1][kk-1] * num[kk];

for(int i = kk+1;i < n;i++)

{

for(int ii = kk-1;ii < i;ii++)

{

temp = field[ii][kk-1] * GET(ii+1,i);

field[i][kk] = field[i][kk] > temp? field[i][kk] : temp;

}

}

}

// PUT();

cout << field[n-1][k];

return 0;

}

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台