UVA 607-Scheduling Lectures(線形dp)

タイトルクリックでリンクを開く
テーマ:
あなたは1つの学校で教えて、毎节の授业の时间はL长くて、あなたはnつのテーマが终わらなければならなくて、すべてのテーマは时々tiです.
2つの制限があります:1、各テーマは1つの授業内でしか話せません.複数の授業に分けられません.2、テーマ順に言わなければならない.
授業ごとに、テーマを話す内容に時間tが残り、t>10であれば、不満度(t-10)^2が生じる、1<=t<=10であれば、学生は喜ぶので、不満度が負の数の-Cが生じる、t=0であれば、不満度は0となる.
すべてのテーマを話し終わったら、少なくとも何時間の授業を使いますか.複数の案があれば、不満度が最も低いことが要求される.
分析:
num[i]はi番目のトピックを記述し、使用する最小レッスンidx[i]はi個のトピックを記述し、num[i]のセクションの最低不満度でnumをdpして最小レッスンを求め、配列初期化INF num[i]=min{num[k]+DI(k,i)、1<=k<=i}は状況に応じてidx配列を保存する
コード:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

int n, L, C, t[MAXN];
int num[MAXN], idx[MAXN], sum[MAXN];


int getDI(int tt){
    if(tt==0) return 0;
    else if(tt>=1 && tt<=10) return -C;
    else return (tt-10)*(tt-10);
}

int main(){

    int cas = 1;
    while(~scanf("%d", &n) && n){

        scanf("%d%d", &L, &C);
        for(int i=1; i<=n; ++i){
            scanf("%d", &t[i]);
            sum[i] = sum[i-1] + t[i];
        }



        for(int i=1; i<=n; ++i){
            num[i] = idx[i] = INF;

            for(int j=1; j<=i; ++j){
                if(sum[i]-sum[j-1] <= L){

                    int DI = getDI(L-(sum[i]-sum[j-1]));

                    if(num[j-1]+1 < num[i]){
                        num[i] = num[j-1] + 1;
                        idx[i] = idx[j-1] + DI;
                    }else if(num[j-1]+1 == num[i]){
                        idx[i] = min(idx[i], idx[j-1]+DI); 
                    }
                }
            }
        }
        if(cas!=1) puts("");
        printf("Case %d:
", cas++);
        printf("Minimum number of lectures: %d
", num[n]); 
        printf("Total dissatisfaction index: %d
", idx[n]);
    }

    return 0;
}