题解 - Vijos

2

最高找 LV 10 @ 2018-09-07 15:12:52

两边平行于i，j轴类似于P1057盖房子
一边平行的可由两个两边平行的拼得
dp[i][j][1--4]为两边平行于i，j轴的三角形
dp[i][j][5--8]为只有一边平行于坐标轴的三角形
最后对所有三角形累和即可


#include<iostream>
#include<cstdio>
using namespace std;
int s[105][105][30][3],n,dp[105][105][9],u[30],res[30],ans;
char juz[105][105];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf(" %c",&juz[i][j]);         
            u[juz[i][j]-'A'+1]=1;
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=n;j>=1;j--)
        {
            if(juz[i+1][j]==juz[i][j] && juz[i][j+1]==juz[i][j])
            dp[i][j][1]=min(dp[i+1][j][1],dp[i][j+1][1])+1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=n;j>=1;j--)
        {
            if(juz[i-1][j]==juz[i][j] && juz[i][j+1]==juz[i][j])
            dp[i][j][2]=min(dp[i-1][j][2],dp[i][j+1][2])+1;
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            if(juz[i+1][j]==juz[i][j] && juz[i][j-1]==juz[i][j])
            dp[i][j][3]=min(dp[i+1][j][3],dp[i][j-1][3])+1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(juz[i-1][j]==juz[i][j] && juz[i][j-1]==juz[i][j])
            dp[i][j][4]=min(dp[i-1][j][4],dp[i][j-1][4])+1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(juz[i-1][j]==juz[i][j] && juz[i][j-1]==juz[i][j] && juz[i+1][j]==juz[i][j])
            dp[i][j][5]=min(dp[i][j][3],dp[i][j][4]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(juz[i+1][j]==juz[i][j] && juz[i-1][j]==juz[i][j] && juz[i][j+1]==juz[i][j])
            dp[i][j][6]=min(dp[i][j][1],dp[i][j][2]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(juz[i][j+1]==juz[i][j] && juz[i][j-1]==juz[i][j] && juz[i-1][j]==juz[i][j])
            dp[i][j][7]=min(dp[i][j][4],dp[i][j][2]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(juz[i+1][j]==juz[i][j] && juz[i][j+1]==juz[i][j] && juz[i][j-1]==juz[i][j])
            dp[i][j][8]=min(dp[i][j][1],dp[i][j][3]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=8;k++)
            {
                ans+=dp[i][j][k];
                int w=juz[i][j]-'A'+1;
                res[w]+=dp[i][j][k];
            }
        }
    }
    printf("%d\n",ans);
    for(int i=1;i<=26;i++)
    {
        if(u[i])
        {
            printf("%c %d\n",i+'A'-1,res[i]);
        }
    }
    return 0;
}

0

swm LV 10 @ 2015-07-25 17:47:09

当年一场什么比赛上写过这题，当时用的是各种递推，以这种三角形为例：
A
AA
AAA
AAAA
用m[i][j]表示以点i,j为顶点的该形状等腰三角形个数，如果i,j的字母与i-1,j相同，则m[i][j]=min(m[i-1][j]+1,a[i][j]-1)其中a[i][j]表示从i,j出发向右与i,j字母相同的连续点个数，这是可以预处理出来的。其他三角形可以类推。不过有特例，对于：
A
AAA
AAAAA
状的三角形，用k[i][j]表示以i,j为底边中点的三角形个数，k[i][i]=min(m[i][j],p[i][j])，这里m[i][j]就是上面提到的三角形，p[i][j]是将m左右翻转后得到的三角形的形状的个数。
ps:那次比赛笔者AK了哦……

0

玛维-影之歌 LV 10 @ 2009-10-15 18:45:17

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 197ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：197ms

用什麼DP 直接模擬117行

編起來有點麻煩還好一次AC了不然調試要累死

第一種情況有一邊相等就說明可以合成一個第2種這樣就不用統計兩次了快很多

0

notblack LV 10 @ 2009-10-14 21:40:49

这题动归的话加上旋转的公式也看的头晕，一个地方少打了个i找了半天。

硬做吧！

0

jacklv LV 10 @ 2009-10-10 12:25:30

50+

dp分两种，f，g

加旋转，每次只考虑一种即可

0

new world LV 10 @ 2009-09-24 17:40:10

三维数组,注意细节!!

0

sunl羽翼 LV 9 @ 2009-09-23 17:39:39

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

cool!一次AC，不过真够囧的，135行；

汗!...

cin>>n;

for(int i=1;imap[i][j];

for(int i=1;i

0

NaTuReHugh LV 9 @ 2009-08-21 21:22:58

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

60+行，开始130+，都不知道怎么写的那么冲动了都；

Program P1403;

var a:array[0..200,0..200] of char;

f:array[0..200,0..200,1..2] of longint;

ans:array['A'..'Z'] of longint;

jj,tot,i,j,n,m:longint;

ch:char;

function min(a,b:longint):longint;

begin if a>b then exit(b) else exit(a); end;

function min2(a,b,c:longint):longint;

begin

min2:=a;

if b

0

raoyu LV 9 @ 2009-08-16 17:41:25

枚举2种不同三角形的4个方向，对于第k种情况(1

0

gyh LV 10 @ 2009-08-13 20:52:31

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

幸福啊

0

xusc_2009 LV 9 @ 2009-08-08 11:24:19

555 少打四个字，没有预处理，结果调了2个小时，交了6遍…………

本人采用最笨的枚举法：1、枚举每一种情况，虽然大多是复制粘贴（但我就是这样子错了）2、枚举当前三角形的高度，程序可以写到123行

本来应该是一道很有纪念意义的100题，但是被1604抢去了，就算纪念第101题吧

0

zhanghanyuan LV 10 @ 2009-08-04 16:04:32

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

同楼下，MS

0

cass6 LV 9 @ 2009-07-27 20:51:40

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

一不小心秒杀了.....

Accepted 有效得分：100 有效耗时：0ms

var a:array[0..100,0..100]of char; p:array['A'..'Z']of boolean; t:array['A'..'Z']of longint;

f:array[0..100,0..100,0..10]of longint; n,i,j,k,s:longint; c:char;

function min1(a,b:longint):longint;

begin if a

0

oimaster LV 10 @ 2009-06-18 19:21:51

复制粘贴出来的……

p.s. 一段写错了改8段……

0

boyzkk LV 10 @ 2009-05-02 09:37:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 322ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：322ms

一次AC！！！

0

luyifan LV 10 @ 2009-04-28 18:59:22

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 40ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

我只知道o(n^3)不知怎样o(n^2)dp

0

yby.barty LV 9 @ 2009-03-17 23:33:35

呃……超时……以后再改吧

#include

using namespace std;

int map[101][101],dat[101][101][4],n,cnt[26],sum=0,step[4][2]={{1,0},{0,-1},{-1,0},{0,1}};

bool app[26];

int go(int x,int y,int dr,int cl)

{

int tmp=0,dx1=x+step[dr][0],dy1=y+step[dr][1],dx2=x+step[(dr+1)%4][0],dy2=y+step[(dr+1)%4][1],d1,d2;

if ((dx1n)||(dy1n)||(dx2n)||(dy2n)) return 0;

if ((map[dx1][dy1]==cl)&&(map[dx2][dy2]==cl)) return min(go(dx1,dy1,dr,cl),go(dx2,dy2,dr,cl))+1;

return 0;

}

int main()

{

memset(cnt,0,sizeof(cnt));

memset(dat,0,sizeof(dat));

memset(app,0,sizeof(app));

cin>>n;

for (int i=1;ic;

map[i][j]=c-'A';

app[map[i][j]]=true;

}

for (int i=1;i

0

xuketian LV 9 @ 2008-11-05 13:51:56

= =|看到一模一样的一题，数据到600，炸了。。。

0

fammiebright LV 9 @ 2008-10-31 09:06:28

非常容易的DP O(n^2)

Accepted 有效得分：100 有效耗时：0ms

0

fengyi LV 9 @ 2008-10-30 21:44:21

原来可以旋转..

膜拜lyyztt67神牛

题解

38 条题解

三角形

信息

状态

开发

支持

题解

38 条题解

三角形

信息

状态

开发

支持

还没有账户？

登录