[NOIP 2014] 서브 매트릭스 문제 풀이 보고서
f(i,j)=lsi+min1≤k
= 여기 서 실제로 또 하나의 문 제 는 모든 그룹의 시간 복잡 도가 얼마나 되 는 지 를 찾아내 는 것 입 니 다. 우 리 는 n 개의 숫자 중에서 m 개 를 선택 합 니 다. 우 리 는 예전 에 01 꼬치 를 검색 하 는 방식 으로 두 개의 가지치기 를 사용 합 니 다. 만약 에 현재 찾 아 낸 1 의 개수 가 m 보다 크 면 가 지 를 자 릅 니 다. 만약 에 남 은 수의 개수 가 모두 1 을 선택 하 더 라 도 m 개 를 모 으 기 에는 부족 하면 가 지 를 자 릅 니 다. 그러면 저 는 가 지 를 자 릅 니 다.이 두 가지 가 지 를 자 르 는 효 과 를 분석 하려 고 합 니 다. 첫 번 째 가 지 를 자 르 는 것 은 좋 습 니 다. 두 번 째 가 지 를 자 르 면 우 리 는 m - x 개가 남 았 을 때 줄 어 든 잎 노드 의 수 (m - (x - 1) 를 고려 하면 이런 뚜렷 한 식 을 얻 을 수 있 습 니 다.
O(∑0≤i≤mCin−∑1≤i≤mCi−1n−(m−i)−1∗2m−i)
이 물건 은 보기에 상당히 큰 것 같다.
그 러 니까
각 그룹의 시간 은 O (1) 입 니 다!
이것 은 상당히 놀 라 운 결론 이 라 고 말 해 야 한다. 우 리 는 이 결론, 즉 등식 을 증명 하려 고 시도 했다.
∑0≤i≤mCin−∑1≤i≤mCi−1n−(m−i)−1∗2m−i=Cmn
, 우 리 는 그것 을 변형 시 켰 다.
∑0≤i
Cmn 은 사실 왼쪽 을 지 났 기 때문에 우 리 는 차라리 그것 을 잘 랐 다.
∑0≤i
∑ 같은 범 위 를 사용 할 수 있 을 것 같 아서 뒤의
∑, 우 리 는 i + 1 대 i 로 i 의 범 위 를 [1, m] 에서 [0, m) 로 미 루 었 다.
그러나 2 의 멱 과 조합 수 를 곱 하면 나 는 이런 물건 을 처리 하지 않 을 것 이다. 이것 은 나 를 매우 아 프 게 한다. 그러나 우리 가 그것들 을 양 휘 삼각형 에 놓 으 면 오른쪽 이 왼쪽 위 에 있 는 계수 가 있 는 사선 이라는 것 을 발견 한다. 그래서 우 리 는 n 행 계수 가 모두 1 로 위로 밀어 올 리 기 시작 했다. 이때 우 리 는 n - 1 행 의 계수 가 2... 21 (m - 1 개 2) 이라는 것 을 놀 라 게 발견 했다.그리고 경계 가 바로 왼쪽 의 첫 번 째 항목 이 고 n - 2 줄 의 계 수 는 4... 42 (m - 2 개 4) 이기 때문에 우 리 는 이런 엄밀 하지 않 은 방식 으로 상기 신기 한 시간 복잡 도 를 증명 할 수 있 을 것 같다!
Code（dfs）：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,r,c;
int a[20][20];
int ls[20],hs[20][20];
int list[20];
int ans=0x7fffffff;
inline void ldfs(int x,int last,int nowc,int nowsum){
if(m-x<nowc||nowsum>=ans)return;
if(x==m){
ans=min(ans,nowsum);
return;
}
ldfs(x+1,last,nowc,nowsum);
if(nowc)ldfs(x+1,x,nowc-1,nowsum+ls[x]+hs[last][x]);
}
inline void hdfs(int x,int now){
if(n-x<now)return;
if(x==n){
int i,j;
memset(ls,0,sizeof(ls));
for(i=m;i--;)
for(j=r;--j;)
ls[i]+=abs(a[list[j]][i]-a[list[j-1]][i]);
int k;
memset(hs,0,sizeof(hs));
for(i=0;i<m;++i)
for(j=i+1;j<m;++j)
for(k=r;k--;)
hs[i][j]+=abs(a[list[k]][i]-a[list[k]][j]);
ldfs(0,m-1,c,0);
return;
}
hdfs(x+1,now);
if(now){
list[--now]=x;
hdfs(x+1,now);
}
}
int main(){
freopen("submatrix.in","r",stdin);
freopen("submatrix.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&r,&c);
int i,j;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
scanf("%d",a[i]+j);
hdfs(0,r);
printf("%d
",ans);
}Code（DP）：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,r,c;
int a[20][20];
int ls[20],hs[20][20];
int list[20];
int ans=0x7fffffff;
int f[20][20];
inline void ldfs(int x,int last,int nowc,int nowsum){
int i,j;
for(i=0;i<m;++i)
for(j=0;j<=c;++j)
f[i][j]=1E9;
for(i=0;i<m;++i)f[0][0]=0,f[i][1]=ls[i];
int k;
for(i=1;i<m;++i)
for(j=2;j<=c;++j){
for(k=0;k<i;++k)f[i][j]=min(f[i][j],f[k][j-1]+hs[k][i]);
f[i][j]+=ls[i];
}
for(i=0;i<m;++i)ans=min(ans,f[i][c]);
}
inline void hdfs(int x,int now){
if(n-x<now)return;
if(x==n){
int i,j;
memset(ls,0,sizeof(ls));
for(i=m;i--;)
for(j=r;--j;)
ls[i]+=abs(a[list[j]][i]-a[list[j-1]][i]);
int k;
memset(hs,0,sizeof(hs));
for(i=0;i<m;++i)
for(j=i+1;j<m;++j)
for(k=r;k--;)
hs[i][j]+=abs(a[list[k]][i]-a[list[k]][j]);
ldfs(0,m-1,c,0);
return;
}
hdfs(x+1,now);
if(now){
list[--now]=x;
hdfs(x+1,now);
}
}
int main(){
freopen("submatrix.in","r",stdin);
freopen("submatrix.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&r,&c);
int i,j;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
scanf("%d",a[i]+j);
hdfs(0,r);
printf("%d
",ans);
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ] 5568 카드 놓기아이디어 Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고 sb에 고른 카드를 담도록 하였다. 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
