0
已解决
被禁言
中级光能
不知道二维的前缀和f[i][j]等于啥，求f[i][j]=?
何冯成在2020-07-23 22:59:12追加了内容
@陶旭杰 RE
#include<iostream>
using namespace std;
long long f[11000][11000],a[11000][11000];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<f[i][j]<<' ';
}
cout<<endl;
}
return 0;
}
何冯成在2020-07-23 23:24:31追加了内容
我自己改了改，AC了，但是这个时间
望大佬再给优化优化
0
已采纳
初级天翼
数组的前缀和还难吗？这个和那个金字塔一类题目的代码很像
还有时间复杂度不达到200ms以上都不太会有大问题，不要降得太低，能过能AC就行了
0
中级光能
应该是：（黄色的面积+蓝色的面积）+（黄色的面积+灰色的面积）-黄色的面积+当前数组元素值a[i][j]
f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j]
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j]
0
初级光能
呵呵，哪有人回发AC代码啊？
白嫖谢谢
0
资深光能
@何冯成 你竟然RE?! 你不怕LU老师。。。。（like that:）
0
中级天翼
时间复杂度一压到最低，不能优化了
0
新手启示者
111
