关于AC dog的介绍
2024-09-22 13:16:39
发布于：浙江
64阅读
0回复
0点赞
在A.13（传纸条）中，我给出了
#include<bits/stdc++.h>
using namespace std;
int n,m,a[55][55],f[55][55][55];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
memset(f,0xcf,sizeof(f));
f[1][1][1]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int x=i+1;x<=n;x++)
{
int y=i+j-x;
f[i][j][x]=a[i][j]+a[x][y]+
max(max(f[i-1][j][x-1],f[i-1][j][x]),
max(f[i][j-1][x-1],f[i][j-1][x]));
}
}
}
f[n][m][n]=f[n-1][m][n];
printf("%d\n",f[n-1][m][n]);
return 0;
}
的AC解，但我问AC狗是否有更优解？AC狗给出了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[55][55];
ll dp1[55][55], dp2[55][55];
int main() {
cin >> n >> m;
for (int i;i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
// dp1[i][j] 表示从(1,1)到(i,j)的最大好感度
dp1[1][1] = a[1][1];
for (int i <= n; i++)
for (int j = 1; j <= m; j++)
if (i + j > 2)
dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1]) + a[i][j];
// dp2[i][j] 表示从(m,n)到(i,j)的最大好感度
dp2[n][m] = a[n][m];
for (int i = n; i >= 1; i--)
for (int j = m; j >= 1; j--)
if (i + j < n + m)
dp2[i][j] = max(dp2[i + 1][j], dp2[i][j + 1]) + a[i][j];
// 枚举两个路径相交的点
ll ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans = max(ans, dp1[i][j] + dp2[i][j]);
cout << ans << endl;
return 0;
}
结果WA声连天（还报错），问他为什么错，他说是数组越界，无语死了😓
不信去看未通过 2024-09-22 13:07:31 0ms 0.00KB C++ 赵依然 左右的几个，都是我的，只有第一个对了……
有帮助，赞一个