제목: n개의 길이 <=11의 012만 포함된 열을 제시하고 2개의 열의 거리를 대응하는 위치가 줄어드는 절대값의 합으로 정의합니다.거리 0에서 2를 구하다×m-1의 대수.
방법: 생각하기 어려운 형태의 압력 dp.각 열의 거리가 x인 몇 개만 계산하면 마지막 답을 구할 수 있다.한꺼번에 문제를 고려하면 우리는 뒷자리와의 거리가 x인 몇 개만 고려할 수 있다. 그러나 이렇게 하면 점차적으로 미룰 수 없다. 앞의 것을 모르기 때문에 우리는 앞의 것을 보완할 수 있다. 그래서 dp[s1][s2][k]는 일부 줄의 접두사가 바로 s1이고 s1+s2라는 줄과의 거리는 k의 개수이다.우리는 |s1|+|s2|=m를 발견할 수 있기 때문에 앞의 2차원을 1차원으로 바꿀 수 있다.
만약 브러시법을 사용한다면 문제풀이 작성법처럼 9가지 상황이 있을 필요가 없다. 단지 3가지 상황만 있고, i위를 0, 1, 2로 생각하면 된다.
i위가 1이라고 가정하면 옮기면
1.dp[s1-'1']['0'+s2][k+1] += dp[s1][s2][k].
2. dp[s1-'1']['1'+s2][k] += dp[s1][s2][k],
3. dp[s1-'1']['2'+s2][k+1] += dp[s1][s2][k].
실제로 쓰는 과정에서 i위를 0, 1, 2로 바꾸면 된다.
초기 값의 설정은 dp[s][공][0]=s라는 열의 개수입니다.
AC 코드:
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll __int64
#define ull unsigned __int64
#define eps 1e-8
#define NMAX 1000000010
#define MOD 1000000007
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI acos(-1)
template
inline void scan_d(T &ret)
{
char c;
int flag = 0;
ret=0;
while(((c=getchar())'9')&&c!='-');
if(c == '-')
{
flag = 1;
c = getchar();
}
while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
if(flag) ret = -ret;
}
const int maxn = 90000+10;
int dp[2][200000][25];
int cnt[200000];
char s[20];
int the[20],m;
ll ans[30];
int main()
{
#ifdef GLQ
freopen("input.txt","r",stdin);
// freopen("o1.txt","w",stdout);
#endif
the[0] = 1;
for(int i = 1; i <= 11; i++) the[i] = the[i-1]*3;
int _t;
scanf("%d",&_t);
while(_t--)
{
int n;
scanf("%d%d",&n,&m);
for(int i = 0; i < the[m]; i++) cnt[i] = 0;
for(int i = 0; i < n; i++)
{
scanf("%s",s);
int x = 0;
for(int j = 0; j < m; j++)
x = x*3+s[j]-'0';
cnt[x]++;
}
int f = 0;
for(int i = 0; i < the[m]; i++)
for(int j = 1; j <= 2*m; j++)
dp[0][i][j] = 0;
for(int i = 0; i < the[m]; i++)
dp[0][i][0] = cnt[i];
for(int i = 0; i < m; i++)
{
for(int j = 0; j < the[m]; j++)
for(int k = 0; k <= 2*m; k++) dp[f^1][j][k] = 0;
for(int j = 0; j < the[m]; j++)
for(int k = 0; k <= 2*m; k++) if(dp[f][j][k])
{
int tmp = j/the[i]%3;
for(int l = 0; l <= 2; l++)
{
int x = j-(tmp-l)*the[i];
dp[f^1][x][k+abs(l-tmp)] += dp[f][j][k];
}
}
f ^= 1;
}
memset(ans,0,sizeof(ans));
for(int i = 0; i < the[m]; i++)
{
if(!cnt[i]) continue;
ans[0] += (ll)cnt[i]*(cnt[i]-1);
for(int j = 1; j <= 2*m; j++)
{
ans[j] += (ll)cnt[i]*dp[f][i][j];
}
}
for(int i = 0; i <= 2*m; i++)
printf("%I64d
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)
python 풀이
DP를 이용해 풀이
보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서
고민을 했는데
이 문구 덕분에 DP 를 이용해 풀이할 수 있었다
뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다
코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
