HDu 1565格子取数(1)
2701 ワード
Problem Description
n*nの格子の碁盤をあげて、各格子の中に非負の数があります.
任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.
Input
複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)を含む.
Output
各テストインスタンスについて、取得可能な最大和を出力します.
Sample Input
Sample Output
Author
ailyanlu
Source
Happy 2007
Recommend
8600
さてLvsi小盆友がセットで試合をして、名前を「虐げに来てくれ」と呼んで、その後リンクを送ってきました・・・狙ってみたら、ほとんどがdp問題だったので、ついでにやったので、虐げてもらえないかな・・・
この問題は簡単で、条件を満たすすべてをふるいにかけて、隣接する2行のdpに従えばいいだけで、典型的な状態はdpを圧縮して、何も言うことはありません......ただ穴のお父さんは複雑さを計算して古い感じがするので、cnt配列を追加しました......
コードを添付
n*nの格子の碁盤をあげて、各格子の中に非負の数があります.
任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.
Input
複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)を含む.
Output
各テストインスタンスについて、取得可能な最大和を出力します.
Sample Input
3
75 15 21
75 15 28
34 70 5
Sample Output
188
Author
ailyanlu
Source
Happy 2007
Recommend
8600
さてLvsi小盆友がセットで試合をして、名前を「虐げに来てくれ」と呼んで、その後リンクを送ってきました・・・狙ってみたら、ほとんどがdp問題だったので、ついでにやったので、虐げてもらえないかな・・・
この問題は簡単で、条件を満たすすべてをふるいにかけて、隣接する2行のdpに従えばいいだけで、典型的な状態はdpを圧縮して、何も言うことはありません......ただ穴のお父さんは複雑さを計算して古い感じがするので、cnt配列を追加しました......
コードを添付
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int map[22][22];
int av[50000];
int dp[22][50000];
int cnt[22][50000];
int main()
{
int i,j,n,up,k,s;
up=0;
for (i=0;i<(1<<20);i++)
{
if ((i & (i<<1))!=0 || (i & (i>>1))!=0) continue;
av[up++]=i;
}
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
scanf("%d",&map[i][j]);
}
}
for (i=0;i<n;i++)
{
for (j=0;j<up && av[j]<(1<<n);j++)
{
cnt[i][j]=0;
for (k=0;k<n;k++)
{
if ((av[j] & (1<<k))!=0) cnt[i][j]+=map[i][k];
}
// printf("%d %d %d
",i,av[j],cnt[i][j]);
}
}
for (i=0;i<up && av[i]<(1<<n);i++)
{
dp[0][i]=cnt[0][i];
}
for (i=1;i<n;i++)
{
for (j=0;j<up && av[j]<(1<<n);j++)
{
for (k=0;k<up && av[k]<(1<<n);k++)
{
if ((av[j] & av[k])!=0) continue;
dp[i][k]=max(dp[i][k],cnt[i][k]+dp[i-1][j]);
}
}
}
s=0;
for (i=0;i<up && av[i]<(1<<n);i++)
{
s=max(s,dp[n-1][i]);
}
printf("%d
",s);
}
return 0;
}