ここから本文です

AOJ 0089番について

caf********さん

2013/3/422:49:49

AOJ 0089番について

以下のコードを提出したら時間切れでした。どうすればいいのか教えて下さい。

#include <stdio.h>
#include <string.h>

int summax=0;
int flag=0;
void solve(int data[][100],int i,int j,int sum,int max,int d);


int main(){

int data[100][100];
char str[1024];
char *tp,temp[2];
int a,c,i,j,d,count,max;

memset(data,-1,sizeof(data));

d=0;
while (scanf("%s",str)!=EOF){
c=0;
tp = strtok( str, "," );
while ( tp != NULL ) {
strcpy(temp,tp);
a=strlen(temp);
if(a==2){data[d][c]=(temp[0]-'0')*10+(temp[1]-'0');}
else{data[d][c]=temp[0]-'0';}
c++;
tp = strtok( NULL,"," );

}
d++;
memset(str,'\0',sizeof(str));
}
count=0;
max=count;
for(j=0;j<100;j++){
for(i=0;i<100;i++){
if(data[j][i]!=-1){count++;}
if(max<count){max=count;}
}
count=0;
}
solve(data,0,0,0,max,d);
printf("%d\n",summax);

return 0;
}

void solve(int data[][100],int i,int j,int sum,int max,int d){

int k,count=0;
if(i==d){
if(sum>summax){summax=sum;}
flag=0;
return;
}
else{
for(k=0;k<100;k++){
if(data[i][k]!=-1){count++;}
}
if(max>count&&flag==0){
solve(data,i+1,j,sum+data[i][j],max,d);
if(j+1<count){solve(data,i+1,j+1,sum+data[i][j+1],max,d);}
}
if(max==count&&flag==0){
solve(data,i+1,j,sum+data[i][j],max,d);
if(j+1<count){solve(data,i+1,j+1,sum+data[i][j+1],max,d);}
flag=1;
}
if(max==count&&flag==1){
solve(data,i+1,j,sum+data[i][j],max,d);
if(j>0){solve(data,i+1,j-1,sum+data[i][j-1],max,d);}
}
if(max>count&&flag==1){
solve(data,i+1,j,sum+data[i][j],max,d);
if(j>0){solve(data,i+1,j-1,sum+data[i][j-1],max,d);}
}
}


}

補足とてもわかりやすいです。

大体わかったと思うのですが、実装で悩んでいます。

max関数を使うというのはわかるのですが・・・

閲覧数:
219
回答数:
1
お礼:
25枚

違反報告

ベストアンサーに選ばれた回答

nar********さん

編集あり2013/3/423:51:20

基本的には、動的計画法で解ける問題です。
上から1行ずつ処理をしていき、
「現在の行までの和の最大値を出す」
ことを目指せば良いです。

具体的には、以下の値が与えられた場合
1
2,3
4,5,6
7,8
9

1行目はそのまま{1}
2行目は1行目の値を加算して{3,4}
3行目は2行目の値を加算して{7,9,10}
4行目も同様に{16,18}
5行目{27}
となり、最大の値は27と求まります。

このように、現在行までの和の最大値と、
次の行配列を引数にし、次行までの和の最大値を返す関数を作ればあっさりと解けます。
先の例でいうと、
{1}と{2,3}を引数に渡すと{3,4}を
{3,4}と{4,5,6}を引数に渡すと{7,9,10}を返すような関数です。


(補足)
次の行aが、現在行bより広がるか狭まるかで、ロジックが変わります。
広がる場合は、まず次行の端の値には、現在行の端の値を足します。
a[0]=a[0]+b[0]
a[a.length-1]=a[a.length-1]+b[b.length-1]
それ以外の値には、現在行の2つの値の内、どちらか大きいものを足します。
a[i]=a[i]+max(b[i-1], b[i])

狭まる場合は、次行に現在行の2つの値の内、どちらか大きいものを足します。
a[i]=a[i]+max(b[i], b[i+1])

こんな感じでわかりますかね。

質問した人からのコメント

2013/3/5 00:29:24

降参 お陰様でAC取れました。ありがとうございました!

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる