我是被这题彻底折腾惨了 。。
DP很简单 不用说了 重点是必须按它那个图说来来划分三角形 而不是随便撇下一部分 随便划下一个三角形就可以
所以 要判断J是第奇数个点才可以
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp1[][],sum[],dp2[][];
char s[][];
int main()
{
int i,j,n;
cin>>n;
for(i = ; i <= n ;i++)
cin>>s[i];
for(i = ; i <= n ;i++)
for(j = ; j < *(n-i+)- ; j++)
if(s[i][j]=='-')
{
dp1[i][j] = ;
dp2[i][j] = ;
}
for(i = ; i <= n ;i++)
{
for(j = ; j < *(n-i+)- ; j++)
{
if(s[i][j]=='-'&&s[i-][j]=='-'&&s[i-][j+]=='-'&&s[i-][j+]=='-')
{
dp1[i][j] = min(dp1[i-][j],min(dp1[i-][j+],dp1[i-][j+]))+;
}
}
}
for(i = n- ; i>= ; i--)
{
for(j = ; j < *(n-i+)- ; j++) if(s[i][j]=='-'&&s[i+][j-]=='-'&&s[i+][j-]=='-'&&s[i+][j]=='-')
dp2[i][j] = min(dp2[i+][j],min(dp2[i+][j-],dp2[i+][j-]))+; }
int ans =;
for(i= ; i <= n ; i++)
for(j = ; j < *(n-i+)-; j++)
{
if(j%==)
ans = max(max(dp1[i][j],dp2[i][j]),ans);
}
sum[] = ;
int re=;
for(i = ; i <= ans ;i++)
{
sum[i] = sum[i-]+;
re+=sum[i];
}
if(ans)
cout<<re<<endl;
else
cout<<"0\n";
return ;
}