【基础练习】【棋盘DP】codevs2193 数字三角形ww题解

矫情吗；* 2022-08-03 00:28 113阅读 0赞

题目描述 Description

数字三角形必须经过某一个点，使之走的路程和最大

输入描述 Input Description

第1行n，表示n行  
第2到n+1行为每个的权值  
程序必须经过n div 2,n div 2这个点

输出描述 Output Description

最大值

样例输入 Sample Input

2  
1  
1 1

样例输出 Sample Output

数据范围及提示 Data Size & Hint

n <=25

今天听卢政荣神犇讲解 才明白这题怎么做 原来只需要将指定必须经过的点加上一个极大值，这样保证经过这个点，最后减去这个点即可

数字三角形ww和www都是这样 因此代码一并放出 区别只是ww是制定n/2,n/2这个点，而www是输入这个点

//codevs2193 数字三角形ww DP
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std; 
    
    const int maxn=30;
    const int bignum=0x3f3f3f3f;
    int a[maxn][maxn],f[maxn][maxn];
    int n;
    
    int main()
    {
    	scanf("%d",&n);
    	for (int i=1;i<=n;i++)
    	{
    		for (int j=1;j<=i;j++)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	a[n/2][n/2]+=bignum;
    	f[1][1]=a[1][1];
    	for (int i=2;i<=n;i++)
    	{
    		for (int j=1;j<=i;j++)
    		{
    			f[i][j]=a[i][j]+max(f[i-1][j],f[i-1][j-1]);
    		}
    	}
    	int ans=0;
    	for (int i=1;i<=n;i++) ans=max(ans,f[n][i]);
    	ans-=bignum;
    	printf("%d",ans);
    	return 0;
    }

//codevs2198 数字三角形www DP
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std; 
    
    const int maxn=30;
    const int bignum=0x3f3f3f3f;
    int a[maxn][maxn],f[maxn][maxn];
    int n,x,y; 
    
    int main()
    {
    	scanf("%d",&n);
    	for (int i=1;i<=n;i++)
    	{
    		for (int j=1;j<=i;j++)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	scanf("%d%d",&x,&y);
    	a[x][y]+=bignum;
    	f[1][1]=a[1][1];
    	for (int i=2;i<=n;i++)
    	{
    		for (int j=1;j<=i;j++)
    		{
    			f[i][j]=a[i][j]+max(f[i-1][j],f[i-1][j-1]);
    		}
    	}
    	int ans=0;
    	for (int i=1;i<=n;i++) ans=max(ans,f[n][i]);
    	ans-=bignum;
    	printf("%d",ans);
    	return 0;
    }