南郵OJ 1154 message
message
時間制限(通常/Java) :
1000 MS/ 3000 MS 実行メモリ制限:65536 KByte
合計コミット:97 テスト合格:47
試合の説明
YMとLINDAは仲の良い友达で同级生で、彼らはいっしょにいていつも话しきれない话题があります.ある素質の開拓活動の中で、クラスの同級生はm行n列の行列を作るように手配したが、YMとLINDAは行列の対角線の両端に配置されたので、彼らは直接話をすることができなかった.幸いなことに、彼らはメモを伝えることで交流することができます.メモは多くの学生を介して相手の手に渡され、YMは行列の左上隅に座り、座標(1,1)、LINDAは行列の右下隅に座り、座標(m,n)である.YMからLINDAに伝わるメモは下または右にしか渡さず、LINDAからYMに伝わるメモは上または左にしか渡さない. イベント中、YMはLINDAにメモを渡し、LINDAから返事をもらうことを望んでいる.クラスの中ですべての学友はすべて彼らを伝达することができて、しかし一回だけ彼らを助けることができて、つまりこの人がYMがLINDAのメモを手渡す时に手伝うならば、LINDAがYMに手渡す时もう手伝いません.逆もまた然り. もう一つ注意したいことがあります.クラス全員が手伝ってくれる好感度が高いか低いか(注意:YMとLINDAの好感度は定義されていません.入力は0で表します)、0-100の自然数で表すことができます.YMとLINDAはできるだけ親切な程度の高い学生を探してメモを伝えるのを手伝ってほしいと思っています.つまり、往復2つのパスを見つけて、この2つのパスの上で学生の親切な程度は最大になります.今、YMとLINDAがこのような2つのパスを見つけるのを助けてください.
入力
入力された最初の行には、スペースで区切られた整数mとnが2つあり、クラスにm行n列(1<=m、n<=50)があることを示します.次のm行はm*nの行列であり、行列中のi行j列目の整数はi行j列目に座っている学生の好意の程度を表す.各行のn個の整数の間をスペースで区切る.
しゅつりょく
出力は1行で、往復2つの道で紙切れを伝える学生の親切さの和の最大値を表す整数が含まれています.
サンプル入力
0 3 9 2 8 5 5 7 0
サンプル出力
34
ヒント
デュアルスレッドダイナミックプランニングの考慮
using namespace std;
const int maxn = 51;
int mp[maxn][maxn];
int dp[maxn * 2][maxn][maxn];
//dp[k][i][j]は、全部でk歩、一つの道(i,k-i)歩、もう一つの道(j,k-j)を歩いたことを表す.
int main(){
int m, n;
cin >> m >> n;
int i, j;
for(i = 1; i <= m;++i){
for(j = 1; j <= n;++j){
cin >> mp[i][j];
}
}
int k;
for(k = 3; k < m + n;++k){
for(i = max(1, k - n); i <= m && i <= k;++i){
for(j = max(i + 1, k - n); j <= m && j <= k;++j){ //j>i重複しないことを保証する
dp[k][i][j] = mp[i][k - i] + mp[j][k - j] +
max(max(dp[k - 1][i][j], dp[k - 1][i - 1][j - 1]),
max(dp[k - 1][i][j - 1], dp[k - 1][i - 1][j]));
}
}
}
int t = m + n; //j>iのため、dp[m+n][m][m]は単独で計算する必要がある
dp[t][m][m] = max(max(dp[t - 1][m][m], dp[t - 1][m - 1][m - 1]),
max(dp[t - 1][m - 1][m], dp[t - 1][m][m - 1]));
cout << dp[t][m][m] << endl;
}
時間制限(通常/Java) :
1000 MS/ 3000 MS 実行メモリ制限:65536 KByte
合計コミット:97 テスト合格:47
試合の説明
YMとLINDAは仲の良い友达で同级生で、彼らはいっしょにいていつも话しきれない话题があります.ある素質の開拓活動の中で、クラスの同級生はm行n列の行列を作るように手配したが、YMとLINDAは行列の対角線の両端に配置されたので、彼らは直接話をすることができなかった.幸いなことに、彼らはメモを伝えることで交流することができます.メモは多くの学生を介して相手の手に渡され、YMは行列の左上隅に座り、座標(1,1)、LINDAは行列の右下隅に座り、座標(m,n)である.YMからLINDAに伝わるメモは下または右にしか渡さず、LINDAからYMに伝わるメモは上または左にしか渡さない. イベント中、YMはLINDAにメモを渡し、LINDAから返事をもらうことを望んでいる.クラスの中ですべての学友はすべて彼らを伝达することができて、しかし一回だけ彼らを助けることができて、つまりこの人がYMがLINDAのメモを手渡す时に手伝うならば、LINDAがYMに手渡す时もう手伝いません.逆もまた然り. もう一つ注意したいことがあります.クラス全員が手伝ってくれる好感度が高いか低いか(注意:YMとLINDAの好感度は定義されていません.入力は0で表します)、0-100の自然数で表すことができます.YMとLINDAはできるだけ親切な程度の高い学生を探してメモを伝えるのを手伝ってほしいと思っています.つまり、往復2つのパスを見つけて、この2つのパスの上で学生の親切な程度は最大になります.今、YMとLINDAがこのような2つのパスを見つけるのを助けてください.
入力
入力された最初の行には、スペースで区切られた整数mとnが2つあり、クラスにm行n列(1<=m、n<=50)があることを示します.次のm行はm*nの行列であり、行列中のi行j列目の整数はi行j列目に座っている学生の好意の程度を表す.各行のn個の整数の間をスペースで区切る.
しゅつりょく
出力は1行で、往復2つの道で紙切れを伝える学生の親切さの和の最大値を表す整数が含まれています.
サンプル入力
0 3 9 2 8 5 5 7 0
サンプル出力
34
ヒント
デュアルスレッドダイナミックプランニングの考慮
/*
* a[0][0] a[m][n], ， ， x,y ，
* dp[k][x1][y1][x2][y2] k ， a[0][0] a[x1][y1] a[x2][y2] ，
*dp[k][x1][y1][x2][y2]=MAX{dp[k-1][x1-1][y1][x2-1][y2],dp[k-1][x1-1][y1][x2][y2-1],
* dp[k-1][x1][y1-1][x2-1][y2],dp[k-1][x1][y1-1][x2][y2-1]}
* x1+y1=x2+y2=k, 。
*dp[k][i][j]： k ， a[i][k-i], a[j][k-j]
*/
using namespace std;
const int maxn = 51;
int mp[maxn][maxn];
int dp[maxn * 2][maxn][maxn];
//dp[k][i][j]は、全部でk歩、一つの道(i,k-i)歩、もう一つの道(j,k-j)を歩いたことを表す.
int main(){
int m, n;
cin >> m >> n;
int i, j;
for(i = 1; i <= m;++i){
for(j = 1; j <= n;++j){
cin >> mp[i][j];
}
}
int k;
for(k = 3; k < m + n;++k){
for(i = max(1, k - n); i <= m && i <= k;++i){
for(j = max(i + 1, k - n); j <= m && j <= k;++j){ //j>i重複しないことを保証する
dp[k][i][j] = mp[i][k - i] + mp[j][k - j] +
max(max(dp[k - 1][i][j], dp[k - 1][i - 1][j - 1]),
max(dp[k - 1][i][j - 1], dp[k - 1][i - 1][j]));
}
}
}
int t = m + n; //j>iのため、dp[m+n][m][m]は単独で計算する必要がある
dp[t][m][m] = max(max(dp[t - 1][m][m], dp[t - 1][m - 1][m - 1]),
max(dp[t - 1][m - 1][m], dp[t - 1][m][m - 1]));
cout << dp[t][m][m] << endl;
}