傳送門
題意：對于n行m列給定的陣列，陣列每個元素的值為0-9，我們需要構造出一個三角形,三角形頂點的坐標即為元素所在的行數和列數，三角形三個頂點的元素值應該相同，對于0-9我們需要分別求出每個數字構造出的三角形的面積最大值*2，額外條件：對于構造出的三角形我們要求其一定要有一條邊平行于行或列，對于每一個點我們還可以任意指定一個元素使其值變為和自己的值相等以方便構造三角形，
思路：首先對于一個給定點我們怎樣使得其構造的三角形面積最大呢？我們已經確定了一個點P，然后我們還可以任選一個點使其值和這個點相等，使其成為構造這個三角形的第二個點，那么我們有兩種方案1.選擇P所在行的最右方的點或最左方的點（誰與P的行數相差大就選誰，保證了一條邊平行）2.選擇P所在列最上方或最下方的點，選出這兩種方案中行數差值最大的或列數差值最大的即為最優的（沒理解可以模擬一下選取程序），那么我們確定了第二個點，對于第三個點其實對于我們所要求的面積我們已經確定了底邊的長度現在我們只需找到和P高度差最大那個點即可，如果我們前面選取的是行數相差最大，那么現在找到列數相差最大的點即可（而其必然是在列數最大的點和列數最小的點中得到，先遍歷一篇預先求出來就好了），然后遍歷所有點求出面積最大值，細節見代碼，
Code
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 4e6 + 25;
ll lst[Max];
int Mod = 1e9 + 7;
struct P
{
P(int a=0, int b=0) :x(a), y(b) { ; }
int x, y;
};
P po[11][Max];
int ma[11][5];//ma[k][1-4]對應分別為值為k的元素中最大的行數、最小的行數、最大的列數、最小的列數
int g[11];//0-9個元素各自的數目
int main()
{
FAST;
int t;cin >> t;
while (t--)
{
int n;cin >> n;
memset(g, 0, sizeof(g));
for (int i = 0;i <= 9;i++)
{
ma[i][1] = -999999;
ma[i][2] = 1e9;
ma[i][3] = -99999;
ma[i][4] = 1e9;
}
for(int i=1;i<=n;i++)
for (int j = 1;j <= n;j++)
{
char kk;cin >> kk;
int k = kk - '0';
if (i > ma[k][1])ma[k][1] = i;
if (i < ma[k][2])ma[k][2] = i;
if (j > ma[k][3])ma[k][3] = j;
if (j < ma[k][4])ma[k][4] = j;
po[k][++g[k]].x = j;po[k][g[k]].y = i;
}
for (int i = 0;i <= 9;i++)
{
int ans = 0;
if (g[i] <= 1) {
cout << 0 << " ";continue;
}
for (int j = 1;j <= g[i];j++)
{
int xt = max(abs(n - po[i][j].x), po[i][j].x - 1);
int yt = max(abs(n - po[i][j].y), po[i][j].y - 1);
ans = max(ans, xt * max(abs(ma[i][2] - po[i][j].y), abs(ma[i][1] - po[i][j].y)));
ans = max(ans, yt * max(abs(ma[i][3] - po[i][j].x), abs(ma[i][4] - po[i][j].x)));
}
cout << ans << " ";
}
cout << endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/230755.html
標籤：其他