ブラシパス-メモ(C言語)
メモをとる
紙切れを伝えるのも技術的な仕事だ.
タイトルの説明
小渕と小軒は親友で同級生で、彼らは一緒にいていつも話が尽きない話題がある.ある素質の開拓活動の中で、クラスの同級生はm行n列の行列を作るように手配したが、小渕と小軒は行列の対角線の両端に配置されたので、彼らは直接話をすることができなかった.幸いなことに、彼らはメモを伝えることで交流することができます.メモは多くの学生を通じて相手の手に伝わり、小渕は行列の左上隅、座標(1,1)、小軒は行列の右下隅、座標(m,n)に座っている.小渕から小軒に伝わるメモは下または右にしか伝わらず、小軒から小渕に伝わるメモは上または左にしか伝わらない.
イベントの進行中、小渕は小軒にメモを渡したいと同時に、小軒に返事をしてほしいと望んでいた.クラスの中ですべての学友はすべて彼らを伝达することができて、しかし一回だけ彼らを助けることができて、つまりこの人が小渕が小軒のメモを渡した时に手伝うならば、小軒が小渕に渡した时に二度と手伝うことはありません.逆もまた然り.
もう一つ注意しなければならないことは、クラス全員が手伝ってくれる好感度が高いか低いか(注意:小渕と小軒の好意の程度は定義されていないので、入力時に0で表す)、1つの[000]内の自然数で表すことができ、数が大きいほど好意を表すことができる.小渕と小軒はできるだけ親切な程度の高い同級生を探してメモを伝えるのを手伝ってほしいと思っています.つまり、往復の2つの伝達経路を見つけて、この2つの経路の上で同級生の親切な程度の和を最大にします.今、小渕と小軒がこのような2つの経路を見つけるのを助けてください.
入力フォーマット
1行目には、スペースで区切られた整数mとnが2つあり、クラスにm行n列があることを示します.
次のm行はm×nの行列、行列中のi行j列目の整数は、i行j列目に座っている学生の好意の程度を表す.各行のn個の整数の間をスペースで区切る.
出力フォーマット
出力ファイルは1行1つの整数で、往復2つの道で紙切れの伝達に参加した学生の好意の程度の和の最大値を表す.
入出力サンプル
入力#1
3 3 0 3 9 2 8 5 5 7 0
出力#1
34
C++
紙切れを伝えるのも技術的な仕事だ.
タイトルの説明
小渕と小軒は親友で同級生で、彼らは一緒にいていつも話が尽きない話題がある.ある素質の開拓活動の中で、クラスの同級生はm行n列の行列を作るように手配したが、小渕と小軒は行列の対角線の両端に配置されたので、彼らは直接話をすることができなかった.幸いなことに、彼らはメモを伝えることで交流することができます.メモは多くの学生を通じて相手の手に伝わり、小渕は行列の左上隅、座標(1,1)、小軒は行列の右下隅、座標(m,n)に座っている.小渕から小軒に伝わるメモは下または右にしか伝わらず、小軒から小渕に伝わるメモは上または左にしか伝わらない.
イベントの進行中、小渕は小軒にメモを渡したいと同時に、小軒に返事をしてほしいと望んでいた.クラスの中ですべての学友はすべて彼らを伝达することができて、しかし一回だけ彼らを助けることができて、つまりこの人が小渕が小軒のメモを渡した时に手伝うならば、小軒が小渕に渡した时に二度と手伝うことはありません.逆もまた然り.
もう一つ注意しなければならないことは、クラス全員が手伝ってくれる好感度が高いか低いか(注意:小渕と小軒の好意の程度は定義されていないので、入力時に0で表す)、1つの[000]内の自然数で表すことができ、数が大きいほど好意を表すことができる.小渕と小軒はできるだけ親切な程度の高い同級生を探してメモを伝えるのを手伝ってほしいと思っています.つまり、往復の2つの伝達経路を見つけて、この2つの経路の上で同級生の親切な程度の和を最大にします.今、小渕と小軒がこのような2つの経路を見つけるのを助けてください.
入力フォーマット
1行目には、スペースで区切られた整数mとnが2つあり、クラスにm行n列があることを示します.
次のm行はm×nの行列、行列中のi行j列目の整数は、i行j列目に座っている学生の好意の程度を表す.各行のn個の整数の間をスペースで区切る.
出力フォーマット
出力ファイルは1行1つの整数で、往復2つの道で紙切れの伝達に参加した学生の好意の程度の和の最大値を表す.
入出力サンプル
入力#1
3 3 0 3 9 2 8 5 5 7 0
出力#1
34
#include
int m,n,a[51][51],f[51][51][100];//f[i][j][p] i , 2 j ,p ;
int max(int x,int y)
{
return x>y?x:y;
}
int min(int x,int y)
{
return x<y?x:y;
}
int main()
{
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=2;i<=m+n-1;i++)
for(int p=max(1,i-m+1);p<=min(i,n);p++)
for(int q=p+1;q<=min(i,n);q++)// ,
f[p][q][i]=max(max(f[p-1][q][i-1],f[p-1][q-1][i-1]),max(f[p][q][i-1],f[p][q-1][i-1]))+a[i-p+1][p]+a[i-q+1][q];
f[n][n][m+n-1]=f[n-1][n][m+n-2]+a[n][m];//
printf("%d
",f[n][n][m+n-1]);
return 0;
}
C++
#include
#include
#include
#include
using namespace std;
const int maxn=60;
int a[maxn][maxn];
int F[2*maxn][maxn][maxn];
int main()
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
//F[sum][i][j]=max{F[sum-1][i][j]...
memset(F,-1,sizeof(F));// -1 ( )
F[2][1][1]=0;// , , 0
for(int k=3;k<m+n;k++)
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
int s=F[k][i][j];
if(F[k-1][i][j]>s)s=F[k-1][i][j];
if(F[k-1][i-1][j]>s)s=F[k-1][i-1][j];
if(F[k-1][i][j-1]>s)s=F[k-1][i][j-1];
if(F[k-1][i-1][j-1]>s)s=F[k-1][i-1][j-1];
if(s==-1)continue;// s -1 , , 。
F[k][i][j]=s+a[k-i][i]+a[k-j][j];// F[k][i][j] 。
}
printf("%d",F[m+n-1][n-1][n]);// i j, ,
// , , 。
return 0;
}