1 数字三角形及衍生

 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include
using namespace std;
const int N=1e3+10;
int f[N][N],w[N][N];//表示到达i,j这个点的步数的集合的最大值
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
       scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
            scanf("%d",&w[i][j]);
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
            f[i][j]=max(f[i][j-1],f[i-1][j])+w[i][j];//从左边或者上面选的最大值
        printf("%d\n",f[n][m]);
    }
    return 0;
}

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

因为限制了2n-1步，故到右下角的点只能往下和往右走，思路跟摘花生的一样 

#include
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int f[N][N],w[N][N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
         cin>>w[i][j];
//因为这题要求求最小值,则初始化周围的数为正无穷
  for(int i=2;i<=n;i++) f[0][i]=INF;
  for(int i=2;i<=n;i++) f[i][0]=INF;
     for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
          f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];//从左边或者上边走的最小值
    cout<

#include
using namespace std;
const int N=11,INF=0x3f3f3f3f;
int f[2*N][N][N],w[N][N];
int main()
{
    int n;
    cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c,a||b||c) w[a][b]=c;
  for(int k=2;k<=n+n;k++)
     for(int i1=1;i1<=n;i1++)
        for(int i2=1;i2<=n;i2++)
         {
             int j1=k-i1,j2=k-i2;//弄出j1和j2
             if(j1>=1&&j1<=n&&j2>=1&&j2<=n)//假如j合法
            {
             int t=w[i1][j1];
             if(i1!=i2) t+=w[i2][j2];//并且不是同个点
             int &x=f[k][i1][i2];
             x=max(x,f[k-1][i1-1][i2-1]+t);//i1和i2向下
             x=max(x,f[k-1][i1-1][i2]+t);//i1向下和i2向右
             x=max(x,f[k-1][i1][i2-1]+t);//i1向右和i2向下
             x=max(x,f[k-1][i1][i2]+t);//i1向右和i2向右
             }
         }
    cout<