nyoj 整理图书

xiaoxiao2021-03-01  9

#include<stdio.h> #include<string.h> using namespace std; #define INF 0x3f3f3f3f int book[1005]; int dp[1005]; int h[1005]; //maxh[i]表示前i堆书被整理后的倒数第一堆的高度(也就是被整理后最高的一堆书的高度) //dp[i]表示前i堆书被整理后所需的最少装订次数 int main(){ int n; int KASE=1; while(scanf("%d",&n)!=EOF){ memset(book,0,sizeof(book)); memset(dp,INF,sizeof(dp)); memset(h,0,sizeof(h)); for(int i=1;i<=n;i++){ int temp; scanf("%d",&temp); book[i]=book[i-1]+temp; } dp[0]=dp[1]=0;//当前0或1摞书不需要装订 for(int i=2;i<=n;i++){ for(int j=i-1;j>=0;j--){ if(h[j]<=book[i]-book[j]){//当前j个中最大高度大于等于从j到i的总书高,进行状态转移 if(dp[i]>dp[j]+i-j-1){ dp[i]=dp[j]+i-j-1; h[i]=book[i]-book[j]; break; } } } } printf("Case %d: %d\n",KASE++,dp[n]); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-3099942.html

最新回复(0)