6439. [GDOI 2020 시뮬레이션 01.17] 소형ω 수열
19533 단어 DP(Dynamic Planning)
제목.
정해
아주 체계적인 피리칼 나무 DP.. 그 절대치를 보면 짜증이 나서 우리는 새로운 이동 방식을 고려했다.숫자를 작은 것부터 큰 것까지 현재 서열의 빈틈에 하나씩 삽입하는 것을 고려하세요.그래서 우리는 이 숫자가 답안에 기여한 바를 알 수 있다.예를 들어 현재 양쪽에 숫자가 없다면 계수는 -2-3-2-2, 한쪽에 숫자가 있다면 계수는 +1-1+1-1-1-1-1-1-1-1 즉 0 0 0이다. 만약 양쪽에 숫자가 있다면 계수는 222이다.물론 경계에 놓인 숫자에 대해서는 특별한 판단이 필요하다.그래서 이런 DP가 생겼다. fi, j, k, tf{i, j, k, t}fi, j, k, t는 전 ii의 개수를 모두 놓고 jj 세그먼트의 서열을 형성했다. 현재의 총 공헌은 kk이다. tt(수치는 0, 1, 2, 0, 2, 0, 2)개의 경계에 있는 ·숫자를 넣었다.이 수를 어디에 삽입해야 하는지, 인접한 구간과 연결되어 있는지 토론해 봅시다.이렇게 하면 DP를 만들 수 있다.모든 방정식을 쓰면 이때 kkk의 수치 범위가 비교적 이상하고 많은 불필요한 상태가 존재하는 것을 발견할 수 있다.kk의 대체품 k′k'k′, k′=k+(2 j -3) a ik'=k+(2j-t)aik′=k+(2j-3-t)ai는 모든 빈자리에 aia 를 채우는 것을 상상해 보는 것과 같다iai가 얻은 총 공헌.이 총 공헌의 정의를 통해 알 수 있듯이 k′k'k′는 비교적 정상적인 수치 범위 내에 있다.매거할 때 매거k′k'k′를 다시 kk로 바꾸고 저장할 때 k′k'k′로 바꾼다.이렇게 하면 시간의 복잡도를 보장할 수 있다.
코드 using namespace std;
#include
#include
#include
#define N 110
#define maxL 1010
#define mo 1000000007
#define ll long long
int n,L;
int a[N];
int f[N][N][maxL][3];
void upd(int i,int j,int k,int t,int val){
// printf("f(%d,%d,%d,%d)+=%d
",i,j,k,t,val);
k=k+(2*j-t)*a[i];
if (k<=L)
(f[i][j][k][t]+=val)%=mo;
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&L);
if (n==1){
printf("1
");
return 0;
}
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
memset(f,0,sizeof f);
f[0][0][0][0]=1;
ll ans=0;
for (int i=0;i<n;++i){
for (int j=0;j<=i;++j)
for (int k=0;k<=L;++k){
for (int t=0;t<=2;++t){
int tmp=f[i][j][k][t];
if (!tmp)
continue;
int rk=k-(2*j-t)*a[i];
// printf("
f(%d,%d,%d,%d)=%d
",i,j,rk,t,f[i][j][k][t]);
// if (i==2 && j==2 && rk==-3 && t==2)
// printf("");
upd(i+1,j+1,rk-2*a[i+1],t,(ll)tmp*(j+1-t)%mo);
if (j)
upd(i+1,j,rk,t,(ll)tmp*(2*j-t)%mo);
if (t<2){
upd(i+1,j+1,rk-a[i+1],t+1,(ll)tmp*(2-t)%mo);
if (j)
upd(i+1,j,rk+a[i+1],t+1,(ll)tmp*(2-t)%mo);
}
if (j>=2)
upd(i+1,j-1,rk+2*a[i+1],t,(ll)tmp*(j-1)%mo);
}
}
}
// printf("
");
for (int k=0;k<=L;++k){
// printf("f(%d,%d,%d,%d)=%d
",n,1,k,2,f[n][1][k][2]);
ans+=f[n][1][k][2];
}
printf("%lld
",ans%mo);
return 0;
}
총결산
카티시안 트리 DP, 즉 순차적으로 삽입하여 전환 중에 연속 세그먼트를 결합합니다.이것은 큰 방법이군..
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
6439. [GDOI 2020 시뮬레이션 01.17] 소형ω 수열
아주 체계적인 피리칼 나무 DP..
그 절대치를 보면 짜증이 나서 우리는 새로운 이동 방식을 고려했다.숫자를 작은 것부터 큰 것까지 현재 서열의 빈틈에 하나씩 삽입하는 것을 고려하세요.그래서 우리는 이 숫자가 답안에...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
아주 체계적인 피리칼 나무 DP.. 그 절대치를 보면 짜증이 나서 우리는 새로운 이동 방식을 고려했다.숫자를 작은 것부터 큰 것까지 현재 서열의 빈틈에 하나씩 삽입하는 것을 고려하세요.그래서 우리는 이 숫자가 답안에 기여한 바를 알 수 있다.예를 들어 현재 양쪽에 숫자가 없다면 계수는 -2-3-2-2, 한쪽에 숫자가 있다면 계수는 +1-1+1-1-1-1-1-1-1-1 즉 0 0 0이다. 만약 양쪽에 숫자가 있다면 계수는 222이다.물론 경계에 놓인 숫자에 대해서는 특별한 판단이 필요하다.그래서 이런 DP가 생겼다. fi, j, k, tf{i, j, k, t}fi, j, k, t는 전 ii의 개수를 모두 놓고 jj 세그먼트의 서열을 형성했다. 현재의 총 공헌은 kk이다. tt(수치는 0, 1, 2, 0, 2, 0, 2)개의 경계에 있는 ·숫자를 넣었다.이 수를 어디에 삽입해야 하는지, 인접한 구간과 연결되어 있는지 토론해 봅시다.이렇게 하면 DP를 만들 수 있다.모든 방정식을 쓰면 이때 kkk의 수치 범위가 비교적 이상하고 많은 불필요한 상태가 존재하는 것을 발견할 수 있다.kk의 대체품 k′k'k′, k′=k+(2 j -3) a ik'=k+(2j-t)aik′=k+(2j-3-t)ai는 모든 빈자리에 aia 를 채우는 것을 상상해 보는 것과 같다iai가 얻은 총 공헌.이 총 공헌의 정의를 통해 알 수 있듯이 k′k'k′는 비교적 정상적인 수치 범위 내에 있다.매거할 때 매거k′k'k′를 다시 kk로 바꾸고 저장할 때 k′k'k′로 바꾼다.이렇게 하면 시간의 복잡도를 보장할 수 있다.
코드 using namespace std;
#include
#include
#include
#define N 110
#define maxL 1010
#define mo 1000000007
#define ll long long
int n,L;
int a[N];
int f[N][N][maxL][3];
void upd(int i,int j,int k,int t,int val){
// printf("f(%d,%d,%d,%d)+=%d
",i,j,k,t,val);
k=k+(2*j-t)*a[i];
if (k<=L)
(f[i][j][k][t]+=val)%=mo;
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&L);
if (n==1){
printf("1
");
return 0;
}
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
memset(f,0,sizeof f);
f[0][0][0][0]=1;
ll ans=0;
for (int i=0;i<n;++i){
for (int j=0;j<=i;++j)
for (int k=0;k<=L;++k){
for (int t=0;t<=2;++t){
int tmp=f[i][j][k][t];
if (!tmp)
continue;
int rk=k-(2*j-t)*a[i];
// printf("
f(%d,%d,%d,%d)=%d
",i,j,rk,t,f[i][j][k][t]);
// if (i==2 && j==2 && rk==-3 && t==2)
// printf("");
upd(i+1,j+1,rk-2*a[i+1],t,(ll)tmp*(j+1-t)%mo);
if (j)
upd(i+1,j,rk,t,(ll)tmp*(2*j-t)%mo);
if (t<2){
upd(i+1,j+1,rk-a[i+1],t+1,(ll)tmp*(2-t)%mo);
if (j)
upd(i+1,j,rk+a[i+1],t+1,(ll)tmp*(2-t)%mo);
}
if (j>=2)
upd(i+1,j-1,rk+2*a[i+1],t,(ll)tmp*(j-1)%mo);
}
}
}
// printf("
");
for (int k=0;k<=L;++k){
// printf("f(%d,%d,%d,%d)=%d
",n,1,k,2,f[n][1][k][2]);
ans+=f[n][1][k][2];
}
printf("%lld
",ans%mo);
return 0;
}
총결산
카티시안 트리 DP, 즉 순차적으로 삽입하여 전환 중에 연속 세그먼트를 결합합니다.이것은 큰 방법이군..
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
6439. [GDOI 2020 시뮬레이션 01.17] 소형ω 수열
아주 체계적인 피리칼 나무 DP..
그 절대치를 보면 짜증이 나서 우리는 새로운 이동 방식을 고려했다.숫자를 작은 것부터 큰 것까지 현재 서열의 빈틈에 하나씩 삽입하는 것을 고려하세요.그래서 우리는 이 숫자가 답안에...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
using namespace std;
#include
#include
#include
#define N 110
#define maxL 1010
#define mo 1000000007
#define ll long long
int n,L;
int a[N];
int f[N][N][maxL][3];
void upd(int i,int j,int k,int t,int val){
// printf("f(%d,%d,%d,%d)+=%d
",i,j,k,t,val);
k=k+(2*j-t)*a[i];
if (k<=L)
(f[i][j][k][t]+=val)%=mo;
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&L);
if (n==1){
printf("1
");
return 0;
}
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
memset(f,0,sizeof f);
f[0][0][0][0]=1;
ll ans=0;
for (int i=0;i<n;++i){
for (int j=0;j<=i;++j)
for (int k=0;k<=L;++k){
for (int t=0;t<=2;++t){
int tmp=f[i][j][k][t];
if (!tmp)
continue;
int rk=k-(2*j-t)*a[i];
// printf("
f(%d,%d,%d,%d)=%d
",i,j,rk,t,f[i][j][k][t]);
// if (i==2 && j==2 && rk==-3 && t==2)
// printf("");
upd(i+1,j+1,rk-2*a[i+1],t,(ll)tmp*(j+1-t)%mo);
if (j)
upd(i+1,j,rk,t,(ll)tmp*(2*j-t)%mo);
if (t<2){
upd(i+1,j+1,rk-a[i+1],t+1,(ll)tmp*(2-t)%mo);
if (j)
upd(i+1,j,rk+a[i+1],t+1,(ll)tmp*(2-t)%mo);
}
if (j>=2)
upd(i+1,j-1,rk+2*a[i+1],t,(ll)tmp*(j-1)%mo);
}
}
}
// printf("
");
for (int k=0;k<=L;++k){
// printf("f(%d,%d,%d,%d)=%d
",n,1,k,2,f[n][1][k][2]);
ans+=f[n][1][k][2];
}
printf("%lld
",ans%mo);
return 0;
}
카티시안 트리 DP, 즉 순차적으로 삽입하여 전환 중에 연속 세그먼트를 결합합니다.이것은 큰 방법이군..
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
6439. [GDOI 2020 시뮬레이션 01.17] 소형ω 수열아주 체계적인 피리칼 나무 DP.. 그 절대치를 보면 짜증이 나서 우리는 새로운 이동 방식을 고려했다.숫자를 작은 것부터 큰 것까지 현재 서열의 빈틈에 하나씩 삽입하는 것을 고려하세요.그래서 우리는 이 숫자가 답안에...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.