2111683 2006-10-20 22:42:27 Accepted 1245 C++ 00:00.12 1004K Crux.D     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;}        

评论