TOJ 4303
2107 단어 ACM 문제 풀이 보고서
http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4303
제목 종류:
동적 기획-다 중 01 가방
데이터 구조:
struct LMIC_CNT
{
int cnt;
int bls[102];
} cnt[32001];사상 분석:
욕심
N 높이 를 맞 추 라 고 했 을 때 가장 적은 블록.
가장 높 은 블록 부터 시작 해서 가장 높 은 블록 을 두 번 째 로 높 은 블록 으로 쓰 고,
이런 사상 은 지 정 된 높이 H 보다 높 아야 만 쓸모 가 있다.
지 정 된 높이 에 도달 하 는 것 은 어떠한 상황 에서 도 정확 할 수 없다.
넓 은 우선 사고:
첫 번 째 단 계 는 M 개의 블록 부터 시작 합 니 다.
첫 번 째 단 계 를 말 하 는 M 개의 블록 이 모두 대열 에 눌 려 있다.
다음 단 계 는 이 단계 에서 대열 이 가장 높 고 쌓 인 나무 에 착안 하여 확대 한다.
모든 노드 는 모든 블록 의 사용 상황 을 기록한다.
이 높이 와 같은 상황 까지 검색 할 때 까지.
하지만 모든 상황 을 검색 해 야 하기 때문에,
그래서 시간 초과 메모리 가 쉽다.
동적 사고:
N 높이 의 최소 블록 을 만들어 달라 고 했 으 니,
높이=1 의 상황 부터 시작 해도 무방 하 다.
기 존의 블록 을 이용 하여 1 부터 N 까지 의 모든 상황 을 구하 세 요.
K 높이 의 최소 나무토막 을 구 해 야 할 때(1)
K 에 게 남 은 모든 나 무 를 빼 고 어떤 상황 이 최소 덩어리 가 필요 한 지,
그리고 기록 하면 현재 다음 층 은 이 층 의 최소 블록 수 를 구하 고 직접 호출 하면 됩 니 다.
증명:
대략.
원본 코드:
#include
#include
#include
#include
using namespace std;
struct LMIC_CNT
{
int cnt;
int bls[102];
} cnt[32001];
void _dpboock(int b[13][2],int n,int t,LMIC_CNT *c)
{
int i,j,k;
//
c[0].cnt=0;
for(i=1;i<=n;i++) c[0].bls[i]=b[i][1];
for(i=1;i<=t;i++)
{
int minc=INT_MAX;
if(i==14)
printf("");
for(j=1;j<=n;j++)
{
if(b[j][0]<=i && c[i-b[j][0]].bls[j]>0)
{
// , +1;
// ,
int temp=c[i-b[j][0]].cnt+1;
if(minc>=temp)
{
minc=temp;
for(k=1;k<=n;k++)
c[i].bls[k]=c[i-b[j][0]].bls[k];
c[i].bls[j]--;
}
}
}
c[i].cnt=minc;
}
printf("%d
",c[i-1].cnt);
}
int main()
{
int i,n,t,blos[14][2]={0};
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++) scanf("%d%d",&blos[i][0],&blos[i][1]);
scanf("%d",&t);
memset(cnt,0,sizeof(cnt));
_dpboock(blos,n,t,cnt);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
poj3080문자열 문 제 는 말 이 야. 물이 너무 많아. STL 이 해결 해!매우 편리 하 다.ps, npos 는. size () 보다 훨씬 좋 으 니 경계 문 제 를 고려 할 필요 가 없습니다.이 코드 는 효율 이 매우 낮...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
