구간 dp 테마 연습
구간 dp 테마 연습
제목의 뜻
1.Equal Sum Partitions
? 이것이야말로 스스로 써라
\[\\]
\[\\]
2.You Are the One
제 지능이 매달리는 것 같아요.
\(dp[i][j]\) 는 현재 빈 창고에 대한\(i\) 부터\(j\) 까지 최소 비용을 표시합니다.
분명히 구간 dp로 생겼는데 어떻게 옮길까요?(스스로 생각해 보라고 조언한다)
하나의\(dp[i][j]\)에 대해 이\(i\)가 가장 먼저 입고되어야 하기 때문에 출고 시간\(k\)을 일일이 열거할 수 있습니다. 그러면 총 공헌은
\[dp[i+1][k]+(k-i)*a[i]+sum[k+1..j]\cdot (k-i+1)\]
즉, 먼저 출고된\(i+1...k\)의 공헌과 +i 자신의 공헌 +\(k+1.j\) 이 부분의 공헌과 그것들이 지연된\(k-i+1\)위의 공헌
rep(i,1,n) rep(j,i+1,n) dp[i][j]=1e9;
rep(i,1,n) dp[i][i]=a[i];
drep(i,n,1)
rep(j,i,n)
rep(k,i,j)
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+(k-i)*a[i]+(k-i+1)*(s[j]-s[k]));
\[\\]
\[\\]
3.Groups
where is my head?
모든 사람의 결정은 사실 한 무리의 사람들을 한 조로 나누는 것이기 때문에 직접 하나하나 간접적으로 올라갈 수 있다
세부 사항: 조건을 만족하는 사람이\(R-L+1\)보다 클 때\(min\)
구간
rep(i,1,n) a[i]=rd(),b[i]=rd();
rep(i,0,n) rep(j,0,n) c[i][j]=0;
rep(i,0,n) dp[i]=0;
rep(i,1,n) c[a[i]][n-b[i]]++;
rep(i,0,n-1) rep(j,i+1,n) dp[j]=max(dp[j],dp[i]+min(j-i,c[i][j]));
printf("%d
",dp[n]);
4.Sky Soldiers
또 가짜 구간
const int N=1010;
const double eps=1e-6;
int n,m;
map M;
typedef map ::iterator iter;
int p[N];
double x[N];
int cnt;
double dp[N][51];// i , j
double sum[N][N];
int main(){
while(~scanf("%d%d",&n,&m)&&n&&m) {
M.clear();
rep(i,1,n) {
rep(j,1,rd()) {
int p=rd();
double x;scanf("%lf",&x);
M[p]+=x;
}
}
cnt=0;
for(iter it=M.begin();it!=M.end();++it) {
p[++cnt]=it->first;
x[cnt]=it->second;
}//
double ans=1e11;
rep(i,0,cnt) rep(j,0,m) dp[i][j]=1e11;
rep(i,1,cnt) rep(j,1,cnt) sum[i][j]=sum[i][j-1]+x[j]*abs(p[i]-p[j]);//
rep(i,1,cnt) dp[i][1]=sum[i][i];
rep(i,1,cnt) {
rep(j,1,m-1) if(dp[i][j]<1e10) {
rep(k,i+1,cnt) {
int mid=(p[i]+p[k])>>1;
mid=lower_bound(p+1,p+cnt+1,mid)-p;
double s=min(sum[i][mid]-sum[i][i]+sum[k][k]-sum[k][mid],sum[i][mid-1]-sum[i][i]+sum[k][k]-sum[k][mid-1]);//
dp[k][j+1]=min(dp[k][j+1],dp[i][j]+s);
}
}
}
rep(i,1,cnt) ans=min(ans,dp[i][m]+sum[i][cnt]-sum[i][i]);
printf("%.2lf
",ans);
}
}
\[\\]
\[\\]
5.Play Game
가짜 구간 dp again
\(dp[l1][r1][l2][r2]\)는 두 서열이 각각\(l1,r1\),\(l2,r2\)의 답이 남았음을 나타낸다. 기초적이지만 디테일이 있다.
int n,m;
int a[N],b[N];
int dp[N][N][N][N];
int sum1[N],sum2[N];
int main(){
rep(kase,1,rd()) {
n=rd();
rep(i,1,n) sum1[i]=a[i]=rd(),sum1[i]+=sum1[i-1];
rep(i,1,n) sum2[i]=b[i]=rd(),sum2[i]+=sum2[i-1];
memset(dp,0,sizeof dp);
drep(l1,n+1,1) rep(r1,l1-1,n) drep(l2,n+1,1) rep(r2,l2-1,n) {
if(l1>r1&&l2>r2) continue;
int s=1e9;
if(l1<=r1) s=min(s,min(dp[l1+1][r1][l2][r2],dp[l1][r1-1][l2][r2]));
if(l2<=r2) s=min(s,min(dp[l1][r1][l2+1][r2],dp[l1][r1][l2][r2-1]));
dp[l1][r1][l2][r2]=sum1[r1]-sum1[l1-1]+sum2[r2]-sum2[l2-1]-s;
}
printf("%d
",dp[1][n][1][n]);
}
}
\[\\]
\[\\]
6.Two Rabbits
이 귀신 문제는 정말 놀랐다.
우선 두 배수 그룹을 연결해서 체인으로 끊어야 돼요.
그 다음에 우리는 제목의 성질을 분석하여 임의의 경로에 대해 서로 중합 역자 서열을 할 때 가장 좋다
즉 점프 경로가 원 서열의 회문 서열일 때 반드시 더 좋다
만약 두 토끼의 경로가 엇갈린다면, 반드시 양쪽으로 계속 뻗을 수 있을 것이다
디테일: 한 점의 회문 길이는 1이고 점프 길이가 n보다 작을 때 답안은 1을 추가합니다
int n,m;
int a[N];
int dp[N][N];
int main(){
srand(618);
while(~scanf("%d",&n)&&n){
rep(i,1,n) a[i]=a[i+n]=rd();
int ans=0;
memset(dp,0,sizeof dp);
rep(l,1,n) drep(i,n*2-l+1,1) {
int j=i+l-1;
if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1]+2-(i==j);
else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
ans=max(ans,dp[i][j]+(l
\[\\]
\[\\]
7.Dire Wolf
이 문제는 그래도 비교적 구간 dp로 생겼다
자신의 이동이 엉뚱하게 틀렸다는 뜻인데...
정확한 이동 방법은 T2와 약간 유사하다. 즉, 마지막으로 죽인 늑대를 일일이 열거하고 앞뒤로 직접 이동한다.
int n,m;
int a[N],b[N];
int dp[N][N];
int main(){
rep(kase,1,rd()){
rep(i,1,n=rd()) a[i]=rd();
rep(i,1,n) b[i]=rd();b[n+1]=a[n+1]=0;
//memset(dp,10,sizeof dp);
drep(i,n,1) rep(j,i,n) {
dp[i][j]=1e9;
if(i==j) dp[i][j]=a[i]+b[i-1]+b[i+1];
else rep(k,i,j) dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]);
// k ,
}
printf("Case #%d: %d
",kase,dp[1][n]);
}
}
\[\\]
\[\\]
8.Dylans loves sequence
이 문제는 나로 하여금 말하고 싶지 않게 한다
int n,m;
int a[N],b[N],cnt;
int s[N],ans[N][N];
void Add(int p,int x){
while(p<=n) s[p]+=x,p+=p&-p;
}
int Que(int p){
int res=0;
while(p) res+=s[p],p-=p&-p;
return res;
}
int main(){
n=rd(),m=rd();
rep(i,1,n) a[i]=b[i]=rd();
sort(b+1,b+n+1),cnt=unique(b+1,b+n+1)-b-1;
rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
rep(l,1,n) {
memset(s,0,sizeof s);
rep(r,l,n) {
ans[l][r]=ans[l][r-1]+r-l-Que(a[r]);
Add(a[r],1);
}
}
rep(i,1,m) {
int x=rd(),y=rd();
printf("%d
",ans[x][y]);
}
}
9.Expression
우선 제목의 뜻을 이해해야 한다
그래서 기호는 임의로 순서를 배정하고 각 기호는 두 개의 수를 합병하는 것과 같다
그래서 총 프로젝트 수는\(n-1)!\
이동도 주의해야 한다. 좌우 두 구간 기호가 교차하여 나타나는 가치를 곱해야 한다
구간\([i,k];[k+1,j]\)를\([i,j]\)에 합칠 때 곱할 공헌은
\[\frac{(j-i-1)!}{(k-i)!*(j-k-1)!}\]
(마지막\(k\) 기호가 고정되어 있으므로\(j-i-1\)
int n,m;
int a[N],opt[N];
ll g[N][N];
ll fac[N]={1},Inv[N]={1,1};
int main(){
rep(i,1,N-1) fac[i]=fac[i-1]*i%P;
rep(i,2,N-1) Inv[i]=1ll*(P-P/i)*Inv[P%i]%P;
rep(i,1,N-1) Inv[i]=Inv[i]*Inv[i-1]%P;
while(~scanf("%d",&n)) {
rep(i,1,n) a[i]=rd();
rep(i,1,n-1) {
char ch;
do ch=getchar();
while(ch!='+'&&ch!='-'&&ch!='*');
if(ch=='+') opt[i]=1;
else if(ch=='-') opt[i]=2;
else opt[i]=3;
}
memset(g,0,sizeof g);
drep(i,n,1) rep(j,i,n) {
if(i==j) g[i][i]=a[i];//
rep(k,i,j-1) {
ll t=Inv[k-i]%P*Inv[j-k-1]%P*fac[j-i-1]%P;
if(opt[k]==1) {
g[i][j]=(g[i][j]+(fac[k-i]*g[k+1][j]%P+fac[j-k-1]*g[i][k]%P)*t)%P;
} else if(opt[k]==2) {
g[i][j]=(g[i][j]+(-1ll*fac[k-i]*g[k+1][j]%P+1ll*fac[j-k-1]*g[i][k]%P)*t)%P;
} else {
g[i][j]=(g[i][j]+g[i][k]*g[k+1][j]%P*t)%P;
}
}
}
printf("%lld
",(g[1][n]%P+P)%P);//
}
}
\[\\]
\[\\]
10.QSC and Master
모두가 알다시피 나는 난동을 잘하는 사람이기 때문에 이 이상한 문제를 나도 난동을 부렸다
그것은 결코 표준적인 구간 dp가 아니다
두 가지 의사 결정:
좌우 단점에서 양쪽으로 직접 확장하기;
이 구간을 잘라라
전체 서열의 답을 구했기 때문에 마지막에 합쳐야 돼요.
int n,m;
int a[N],b[N];
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
ll dp[N][N];
int main(){
rep(kase,1,rd()){
n=rd();
rep(i,1,n) a[i]=rd();
rep(i,1,n) b[i]=rd();
memset(dp,-63,sizeof dp);
drep(i,n,1) rep(j,i+1,n) {
if(j-i==1) {
if(gcd(a[i],a[j])!=1) dp[i][j]=b[i]+b[j];
continue;
}
if(gcd(a[i],a[j])!=1) dp[i][j]=max(dp[i][j],dp[i+1][j-1]+b[i]+b[j]);//
rep(k,i,j) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);//
}
ll ans=0;
rep(i,1,n) {
dp[1][i]=max(dp[1][i],0ll);
rep(j,1,i) dp[1][i]=max(dp[1][i],max(0ll,dp[1][j])+max(0ll,dp[j+1][i]));
}//
rep(i,1,n) rep(j,i,n) ans=max(ans,dp[i][j]);
printf("%lld
",ans);
}
}
\[\\]
\[\\]
11.Kirinriki
오타
const int N=5100,P=1e9+7;
int n,m;
char s[N];
int dp[N];
int main(){
rep(kase,1,rd()){
m=rd();
scanf("%s",s+1);n=strlen(s+1);
int ans=0;
rep(i,3,n*2-1) {
reg int cnt=0,p=1;
drep(j,i/2-(!(i&1)),1) {
if(i-j>n) break;
cnt++;
dp[cnt]=dp[cnt-1]+abs(s[j]-s[i-j]);
while(dp[cnt]-dp[p-1]>m) p++;
ans=max(ans,cnt-p+1);
}
}
printf("%d
",ans);
}
}
\[\\]
\[\\]
12.Zuma
이 문제는 소질이 없다!얘가 자꾸 끊겨!
\(dp[i][j][0...4]\) 표시
0:소진
1:0 하나 남았어요.
2:0 2개 남았어요.
3:1 남았어요. 1.
4:2개 남았어요.
이동이 매우 번거롭다
카드 팁: 서로 인접한 것은 한 덩어리로 눌러도 된다
(내 생각이 틀리지 않았으면 좋겠지)
const int N=410;
#define chk(a,b) (a>b&&(a=b))//
int n,m;
char s[N];
int a[N],b[N],c[N],dp[N][N][5];
//0 --> 0
//1 --> one 0
//2 --> two 0
//3 --> one 1
//4 --> two 1
int main(){
int T; scanf("%d",&T);
rep(kase,1,T){
scanf("%s",s+1);
n=strlen(s+1);
rep(i,1,n) a[i]=s[i]^'0';
int _n=0;
rep(i,1,n) if(i==1||a[i]!=a[i-1]) {
_n++;
b[_n]=1; c[_n]=a[i];
} else b[_n]++,b[_n]=b[_n];//
n=_n;
rep(i,1,n) rep(j,1,n) rep(o,0,4) dp[i][j][o]=1e9;
rep(i,1,n) {
dp[i][i][c[i]*2+b[i]]=0;
dp[i][i][0]=3-b[i];
}//
drep(i,n,1) rep(j,i+1,n) {
rep(k,i,j-1){
reg int *x=dp[i][k],*y=dp[k+1][j];//
chk(dp[i][j][0],x[0]+y[0]);
chk(dp[i][j][0],x[1]+y[2]);
chk(dp[i][j][0],x[2]+y[2]);
chk(dp[i][j][0],x[2]+y[1]);
chk(dp[i][j][0],x[3]+y[4]);
chk(dp[i][j][0],x[4]+y[3]);
chk(dp[i][j][0],x[4]+y[4]);
chk(dp[i][j][1],x[0]+y[1]);
chk(dp[i][j][1],x[1]+y[0]);
chk(dp[i][j][2],x[1]+y[1]);
chk(dp[i][j][2],x[0]+y[2]);
chk(dp[i][j][2],x[2]+y[0]);
chk(dp[i][j][3],x[0]+y[3]);
chk(dp[i][j][3],x[3]+y[0]);
chk(dp[i][j][4],x[3]+y[3]);
chk(dp[i][j][4],x[0]+y[4]);
chk(dp[i][j][4],x[4]+y[0]);
}
chk(dp[i][j][0],dp[i][j][1]+2);
chk(dp[i][j][0],dp[i][j][2]+1);
chk(dp[i][j][0],dp[i][j][3]+2);
chk(dp[i][j][0],dp[i][j][4]+1);
}
printf("Case #%d: %d
",kase,dp[1][n][0]);
}
}
(문제풀이를 반쯤 썼는데 갑자기 Dalao가 나에게 질문을 했는데 이런 방법이 틀린 것 같다는 것을 발견했다..., 아직 옳고 그름은 알 수 없다)
오류가 있으면 댓글로 남겨주세요.
전재 대상:https://www.cnblogs.com/chasedeath/p/11331120.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.