ZJU1161 Gone Fishing - 동적 계획

1989 단어
제목 설명:
한 사람이 n개의 호수에 가서 낚시를 하면 i번째 호수에서 처음에는 한 단위 시간에fi마리를 낚을 수 있고, 다음 단위 시간에 낚는 물고기의 수량은 점차 줄어든다.호수의 배열은 선형으로 i번 호수에서 i+1번 호수까지ti의 시간이 필요하다.현재 m 시간 사용 가능, 첫 번째 호수에서 최대 몇 마리의 물고기를 낚을 수 있는지 물어보세요.
분석:
제목 조건이 무후효성을 충족시키면 동태적인 기획으로 해결할 수 있다는 것이 뚜렷하다.
dp[i][j]를 설정하면 전 i개 호수에서 j를 가장 많이 낚는 시간(그리고 i개 호수에 머무르는 시간)을 나타낸다.getFish(i,t)는 i번째 호수에서 t시간을 들여 총 획득한 물고기의 수를 나타낸다.
상태 이동 방정식: dp[i][j]=max{dp[i-1][j-t[i]-k]+getFish(i,k)}, k는 i번째 호수에서 k시간을 머무르는 것을 나타낸다.
프로그램은 순환 변수의 경계 조건에 특히 주의해야 한다.답답한 건 PE를 두 번이나 하다니...
또한 이 제목은 유여가의 흑서에 나와 있는데 방법은 매거+욕심으로 동적 기획보다 효율이 훨씬 높다는 것이다.
/*
ZJU1161 Gone Fishing
*/

#include 
  
   
#include 
   
     #define N 30 #define M 400 #define clr(a) memset(a,0,sizeof(a)) #define MIN(a,b) ((a)>(b)?(b):(a)) #define MAX(a,b) ((a)>(b)?(a):(b)) int n,m; int f[N],d[N],t[N]; int reach[N]; int dp[N][M]; int ans[N]; int max,mi,mj; int g[N][M]; int getFish(int lake,int time){ if(d[lake]) time = MIN(time , f[lake]/d[lake]+(f[lake]%d[lake]!=0)); if(time==0) return 0; return f[lake]*time - d[lake]*(time*(time-1)/2); } void getAns(int i,int j){ ans[i]=g[i][j]; if(i>1) getAns(i-1,j-g[i][j]-t[i]); } int main() { int T,h; scanf("%d",&T); while(T--){ int newLine=0; while(scanf("%d",&n),n){ //init clr(f); clr(d); clr(t); clr(dp); clr(g); clr(ans); //input int i,j,k; scanf("%d",&h); m=h*12; for(i=1;i<=n;i++) scanf("%d",&f[i]); for(i=1;i<=n;i++) scanf("%d",&d[i]); for(i=2;i<=n;i++) scanf("%d",&t[i]); reach[1]=0; for(i=2;i<=n;i++) reach[i]=t[i]+reach[i-1]; //DP max=0; for(j=0 ;j<=m;j++){ dp[1][j] = getFish(1,j); if(max<=dp[1][j]){ max = dp[1][j]; mi=1; mj=j; } g[1][j]=j; } int num; for(i=2;i<=n;i++){ for(j=m;j>=reach[i];j--){ dp[i][j]=-1; for(k=0;k<=j-reach[i];k++){ num=dp[i-1][j-t[i]-k]+getFish(i,k); if(num>dp[i][j]){ dp[i][j]=num; g[i][j]=k; } } if(max
OpenResty 협정 API 돌리 기
nginx + rsync 로 컬 yum 소스 및 네트워크 yum 소스 실현

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage