1245是一道比较经典的dp。一个大的正三角形，由许多小的三角形组成，他们分为黑白二色。求最大的白色正三角形面积。

    思路不难。把每一行白色的累计数存起来作dp。当然这要分尖朝上的和尖朝下的。朝上的公式是r[i][k] = min(r[i - 1][k - 1] + 1, b[i][k]); b存的是白色的累计数，r是最终的边长。朝下的亦同。

    似乎很简单。可好久没做题了，犯了些低级失误，比如把b和r写反了。我不知道这和越来越近的考研有什么关系——也许我就是在岩壁上紧抓藤蔓的失足者，寒冷的1月就是悬崖下的毒蛇。

    所以......还是要加油了。藤蔓不是这么可靠的，我的数学也一样。

    附程序，写的比较烂，仅供参考。

#include <iostream>
#include <cstring>
using namespace std;

int n, b[101][210], r[101][210], ans;

int min(int a, int b)
{
 return a < b ? a : b;
}

int main()
{
 //freopen("in.txt", "r", stdin);
 int i, k, c = 1;
 while(cin >> n && n)
 { 
  memset(b, 0, sizeof(b));
  memset(r, 0, sizeof(r));
  printf("Triangle #%d\n", c ++);
  for(i = 1; i <= n; i ++)
  {
   int t = 0;
   for(k = i; k <= 2 * n - i; k ++)
   {
    char ch;
    cin >> ch;
    if(ch == '#')
     t = 0;
    else
     t ++;
    b[i][k] = (t + 1) / 2;
   }
  }
  ans = 0;
  for(i = 1; i <= n; i ++)
  {
   for(k = i; k <= 2 * n - i; k ++)
   {
    if((i + k) % 2 == 1)
    {
     r[i][k] = min(r[i - 1][k - 1] + 1, b[i][k]);
     if(ans < r[i][k])
      ans = r[i][k];
    }
   }
  }
  for(i = n; i >= 1; i --)
  {
   for(k = i; k <= 2 * n - i; k ++)
   {
    if((i + k) % 2 == 0)
    {
     r[i][k] = min(r[i + 1][k - 1] + 1, b[i][k]);
     if(ans < r[i][k])
      ans = r[i][k];
    }
   }
  }
  //pb();
  //pr();
  printf("The largest triangle area is %d.\n\n", ans * ans);
 }
 return 0;
}
      

评论