USACO 3.3.4 Home on the Range 家的範圍
本文正體字版由OpenCC轉換
這道題可以動態規劃。二維的動態規劃。
狀態定義：G[i][j]爲以(i,j)爲左上角頂點的正方形的最大邊長。
邊界條件：G[i][j]爲初始讀入的矩陣。
狀態轉移方程： G[i][j]=min{ G[i+1][j] , G[i][j+1] , G[i+1][j+1] } + 1;
解析： G[i+1][j] , G[i][j+1] , G[i+1][j+1]分別爲(i,j)向下、向右、向右下一格的狀況。在(n-1,n-1)當且僅當三者都爲1的時候，正方形才能擴充。從最右下向上，依次擴充即可。
USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: range LANG: C++
Compiling… Compile: OK
Executing… Test 1: TEST OK [0.000 secs, 3088 KB] Test 2: TEST OK [0.011 secs, 3092 KB] Test 3: TEST OK [0.000 secs, 3092 KB] Test 4: TEST OK [0.000 secs, 3092 KB] Test 5: TEST OK [0.022 secs, 3088 KB] Test 6: TEST OK [0.011 secs, 3092 KB] Test 7: TEST OK [0.022 secs, 3088 KB]
All tests OK.
/*
ID: cmykrgb1
PROG: range
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAXN 251
using namespace std;
ifstream fi("range.in");
ofstream fo("range.out");
int G[MAXN][MAXN],n;
long ans[MAXN];
void init()
{
long i,j;
char c;
fi >> n;
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
c=10;
while (c==10 || c==13) c=fi.get();
G[i][j]=c-48;
}
}
}
long min3(long a,long b,long c)
{
long k=a;
if (b<k) k=b;
if (c<k) k=c;
return k;
}
void dynamic()
{
long i,j,k;
for (i=n-1;i>=1;i--)
{
for (j=n-1;j>=1;j--)
{
if (G[i][j])
G[i][j]=min3(G[i+1][j],G[i][j+1],G[i+1][j+1])+1;
if (G[i][j]>1)
for (k=2;k<=G[i][j];k++)
ans[k]++;
}
}
}
void print()
{
long i,j;
for (i=2;i<=MAXN;i++)
{
if (ans[i])
fo << i << ' ' << ans[i] << endl;
}
fi.close();
fo.close();
}
int main()
{
init();
dynamic();
print();
return 0;
}
上次修改時間 2017-02-03