Aresene @ 2021-12-14 16:50:28
求助,一个笨办法(>=10就必定TLE),写递归,但是就一个传值报错整疯了,人都不好了。
已经困扰了我
time_t *t = gettime();
天
#include <bits/stdc++.h>
using namespace std;
int js(int n,int x,int y,int a[][n]){
if(y <= n){
if(x <= y){
int tmp = (a[x][y] + js(n,x,y+1,a)),tmp1 = a[x][y] + js(n,x+1,y+1,a);
return tmp >= tmp1 ? tmp : tmp1;
}else return 0;
}else return 0;
}
int main(){
int n;
cin >> n;
int a[n][n];
for (int i = 1;i <= n;i++)for(int j = 1;j <= i;j++)cin >>a[i][j];
cout << js(n,0,0,a) << endl;
return 0;
}
by Dream_weavers @ 2021-12-14 17:02:32
dp是个好东西,你值得拥有
#include<bits/stdc++.h>
using namespace std;
long long i,j,n,a[1005][1005],f[1005][1005];
int main()
{
cin>>n;
for(i=1;i<=n;i++) for(j=1;j<=i;j++) cin>>a[i][j];
for(i=n;i>0;i--)
{
for(j=1;j<=i;j++)
{
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
}
}cout<<f[1][1];
return 0;
}