第一行,一個自然數(shù)T,表示總共給出的三角形數(shù),對于每一個三角形,首先給出一個自然數(shù)n,表示將輸入的三角形有n行。接下來有n行,第i行有2i-1個數(shù)字,
要求你用筆從第1行畫到第n(0 < n ≤ 100)行,從當前行往下畫的時候只能在相鄰的數(shù)字經(jīng)過,也就是說,如果從一行的一個數(shù)往下畫,只能選擇其左下或者正下或者右下三個數(shù)中的一個(如果存在的話),把所有被畫起來的數(shù)字相加,得到一個和,求能得到的最大的和的值是多少。
上例中能得到的最大的和為3 + 7 + 4 + 9 = 23.
測試樣例:
對于圖上的測試樣例,我的代碼可以完全通過。但是為了保險,我自己又添加了幾組測試數(shù)據(jù),出現(xiàn)了問題:
如果測試兩組數(shù)據(jù),也就是這樣:
<PS:這是ide的運行窗口,白色的數(shù)字代表每組測試數(shù)據(jù)得出的結(jié)果。另外,黑色圖中第二組是我自己添加的測試數(shù)據(jù),也就是下面這組:>
是的,目前看來沒問題,但是讓我們將測試數(shù)據(jù)增加到三組————也就是Sample input的數(shù)據(jù)再加上我自己添加的一組數(shù)據(jù),出問題了:
然而,再單獨運行我添加的一組數(shù)據(jù),結(jié)果又正確了:
下面先貼上代碼:
#include <stdio.h>
int main()
{
int t; //定義一個自然數(shù)t,代表將要測試數(shù)據(jù)的組數(shù)
scanf("%d",&t);
while(t --)
{
int n,sum = 0,i,j;
scanf("%d",&n); //輸入每一組測試數(shù)據(jù)(三角形)的行數(shù)
if(n==1)
{
int num;
scanf("%d",&num);
sum += num;
} //如果只有一行,直接加上輸入的一個數(shù)
else{ //如果不止一行
int flag = 0;
for(i=1;i<=n;i++)
{
int max = 0;
int a[2*i-1]; //每行的數(shù)據(jù)個數(shù)為此行的行數(shù)乘2再減1,那么每跳到一行就定義一個能容納那么多數(shù)的數(shù)組
for(j=0;j<2*i-1;j++)
{
scanf("%d",&a[j]); //輸入2*i-1個數(shù)
}
if(i<=2) //如果行數(shù)在1和2之間,找出每行的最大值,并加到計數(shù)器sum上,知道加完第二行,用flag記錄第二行最大值的位置
{
int k;
max = a[0];
for(k=0;k<2*i-1;k++)
{
if(a[k]>max){
max = a[k];
flag = k;
}
}
sum+=max;
}
else //當行數(shù)在兩行以上
{
int m;
int flag1; //定義一個flag1來更新從第三行開始最大值的位置
max = a[flag];
for(m=flag;m<=flag+2;m++)
{
if(a[m]>max){
max = a[m];
flag1 = m;
}
}
sum += max;
flag = flag1;
}
}
}
printf("%d\n",sum);
}
}
花了一個晚自習(xí)也沒有debug出來,我快瘋了.........
這是一道動態(tài)規(guī)劃的問題,而你使用了貪心算法
使用一個簡單的樣例來反駁:
1
1
1 0 -1
0 0 0 0 10000
大概不用解釋了....
#include <stdio.h>
#include <limits.h>
int a[101];
int fa[101];
int fb[101];
int max(const int f[], int i, int j) //找出可到達(i,j)的最大元素
{
int res = INT_MIN; //負極大
for (int k = -2; k <= 0; k++)
{
if ((j + k) < 1 || (j + k) > 2 * (i - 1) - 1) continue; //處理越界
res = (res <= f[j + k] ? f[j + k] : res); //找到最大的元素
}
return res;
}
int find(const int f[], int n) //找數(shù)組里最大的元素
{
int res = f[1];
for (int i = 2; i <= n; i++)
res = (res <= f[i] ? f[i] : res);
return res;
}
int main()
{
int t; //循環(huán)次數(shù)
scanf("%d", &t);
int n; //三角形層數(shù)
int *pfa; //指向當前行的指針
int *pfb; //指向上一行的指針
int *swap; //用于交換的指針
while (t--)
{
scanf("%d", &n);
scanf("%d", &a[1]);
pfa = fa;
pfb = fb;
pfb[1] = a[1]; //一開始就從第二行開始處理,所以第一行用pfb指向
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= 2 * i - 1; j++)
{
scanf("%d", &a[i]);
pfa[j] = max(pfb, i, j) + a[i]; //動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程核心
}
//交換pfa和pfb的地位,用于節(jié)省空間
swap = pfa;
pfa = pfb;
pfb = swap;
}
printf("%d\n", find(pfb, 2 * n - 1)); //在最后一行里尋找最大的元素,該元素即為結(jié)果
}
return 0;
}
時間復(fù)雜度:t * (n*n*3 + n) => O(n^2)
我的代碼中如何節(jié)省空間(交替使用兩個一維數(shù)組)的部分并不重要,請仔細思考以下部分:
f[1][1] = a[1][1];
f[i][j] = max(f[i-1][j+k]) + a[i][j] 2<=i<=n, 1<=j<=2*i-1, -2<=k<=0 (注意處理j+k的越界)
請拿出筆和紙,隨便找一組數(shù)據(jù),模擬一下。注意這里是直角三角形,不是等腰三角形:)
問題很多,而且你的代碼并沒有達到要求。這個題是要你做樹形檢索,不是找每行的最大值。
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
int main()
{
int t; //定義一個自然數(shù)t,代表將要測試數(shù)據(jù)的組數(shù)
scanf_s("%d", &t);
while (t--)
{
int n, sum = 0, i, j;
scanf_s("%d", &n); //輸入每一組測試數(shù)據(jù)(三角形)的行數(shù)
if (n == 1)
{
int num;
scanf_s("%d", &num);
sum += num;
} //如果只有一行,直接加上輸入的一個數(shù)
else { //如果不止一行
int flag = 0; // ---> flag每層循環(huán)都未初始化,上層的flag傳到下層去了,不知道你這個flag要干什么
for (i = 1;i <= n;i++)
{
int max = 0;
int *a = (int *)malloc(sizeof(int)*(2 * i - 1)); //每行的數(shù)據(jù)個數(shù)為此行的行數(shù)乘2再減1,那么每跳到一行就定義一個能容納那么多數(shù)的數(shù)組
for (j = 0;j<2 * i - 1;j++)
{
scanf_s("%d", &a[j]); //輸入2*i-1個數(shù)
}
if (i <= 2) //如果行數(shù)在1和2之間,找出每行的最大值,并加到計數(shù)器sum上,知道加完第二行,用flag記錄第二行最大值的位置
{
int k;
max = a[0];
for (k = 0;k<2 * i - 1;k++)
{
if (a[k]>max) {
max = a[k];
flag = k;
}
}
sum += max;
}
else //當行數(shù)在兩行以上
{
int m;
int flag1; //定義一個flag1來更新從第三行開始最大值的位置 ---> flag1未賦值,如果你后面的for循環(huán)里的if從未執(zhí)行過,你flag = flag1一定崩潰
max = a[flag];
for (m = flag;m <= flag + 2;m++)
{
if (a[m]>max) {
max = a[m];
flag1 = m;
}
}
sum += max;
flag = flag1;
}
free(a);
a = NULL;
}
}
printf("%d\n", sum);
}
getchar();
return 0;
}
北大青鳥APTECH成立于1999年。依托北京大學(xué)優(yōu)質(zhì)雄厚的教育資源和背景,秉承“教育改變生活”的發(fā)展理念,致力于培養(yǎng)中國IT技能型緊缺人才,是大數(shù)據(jù)專業(yè)的國家
北大青鳥中博軟件學(xué)院創(chuàng)立于2003年,作為華東區(qū)著名互聯(lián)網(wǎng)學(xué)院和江蘇省首批服務(wù)外包人才培訓(xùn)基地,中博成功培育了近30000名軟件工程師走向高薪崗位,合作企業(yè)超4
中公教育集團創(chuàng)建于1999年,經(jīng)過二十年潛心發(fā)展,已由一家北大畢業(yè)生自主創(chuàng)業(yè)的信息技術(shù)與教育服務(wù)機構(gòu),發(fā)展為教育服務(wù)業(yè)的綜合性企業(yè)集團,成為集合面授教學(xué)培訓(xùn)、網(wǎng)
達內(nèi)教育集團成立于2002年,是一家由留學(xué)海歸創(chuàng)辦的高端職業(yè)教育培訓(xùn)機構(gòu),是中國一站式人才培養(yǎng)平臺、一站式人才輸送平臺。2014年4月3日在美國成功上市,融資1
曾工作于聯(lián)想擔任系統(tǒng)開發(fā)工程師,曾在博彥科技股份有限公司擔任項目經(jīng)理從事移動互聯(lián)網(wǎng)管理及研發(fā)工作,曾創(chuàng)辦藍懿科技有限責任公司從事總經(jīng)理職務(wù)負責iOS教學(xué)及管理工作。
浪潮集團項目經(jīng)理。精通Java與.NET 技術(shù), 熟練的跨平臺面向?qū)ο箝_發(fā)經(jīng)驗,技術(shù)功底深厚。 授課風格 授課風格清新自然、條理清晰、主次分明、重點難點突出、引人入勝。
精通HTML5和CSS3;Javascript及主流js庫,具有快速界面開發(fā)的能力,對瀏覽器兼容性、前端性能優(yōu)化等有深入理解。精通網(wǎng)頁制作和網(wǎng)頁游戲開發(fā)。
具有10 年的Java 企業(yè)應(yīng)用開發(fā)經(jīng)驗。曾經(jīng)歷任德國Software AG 技術(shù)顧問,美國Dachieve 系統(tǒng)架構(gòu)師,美國AngelEngineers Inc. 系統(tǒng)架構(gòu)師。