【類貪欲+A littleシミュレーション】UPC~MAXの読書計画

UPC 2020年春混合個人訓練4.26日場
MAXは読書が大好きで、自分の読書計画を立てるために、彼は事前に読む内容をマークして、A Bは1つのページのセグメントを表して、つまりAからBまで、もちろんAには6つのページがある:2-7 1-3-12 12-20 7-10 4-50の連続するページがある:1-3、3-12、12-20の長さは20-1+1=20で3つのページからなる2-7、7-10の長さは10-2+1=9で2つのページからなる4-50の長さは50-4+1=47で1つのページからなる最も長い1つが3つ目なので、結果は47 1である.なお、2つの異なる連続するページセグメント長が同時に最大である場合には、構成ページセグメント数の多い1つをとる.例:1−5,5−10,1−10出力:10 2第1の動作の整数n,n<500を入力する.2行目からn+1行目まで、1行に2つの整数A,Bがあり、1ページ分の情報が記録される.0<=A出力は、最も長いページセグメントの長さと、それを構成するページセグメントの数という整数を出力する.サンプル入力7 1 5 10 12 3 10 2 7 2 10 12 16 7サンプル出力15 3ヒント1-5長さ5は1ページからなる3-10,10-12,12-16長さ14は3ページからなる2-7,7-9長さ8は2ページからなる2-10,10-12,16長さ15は3ページからなる
したがって、出力が最も長いページセグメントの長さである15は、3つのページセグメントからなる
【データ規模】30%のデータに対してn<20、0<=A 100%のデータに対してn<500、0<=Aで問題を解く構想:この問題は何も考えにくいところがないと感じて、しかし私の1日をぼんやりさせて、本当にとても野菜でfor遍歴して、毎回i番目のページで終わる最長のページの連続長さを探して、前提はこのnページのセグメントを保存してそして各ページのセグメントの開始ページ数によって昇順に並べます(これにより、i番目のページセグメントに接続されたページ数が小さいページセグメントがi番目の前にあることを保証します)、i番目のページセグメントで終わる最長のページセグメントの連続長さと最大のページセグメント数を別の配列で格納することに注意します.最初に格納されたデータは動けません.そうしないと、検索中にエラーが発生します.また、問題の要求に注意してください.同じ長さでページセグメント数を多く取ると、この問題はもう少しで解決した.ACソース:

#include
#include
using namespace std;
typedef long long ll;
const int maxn = 510;
int n;
int b[maxn],c[maxn];
struct node{
    int st,ed,num;  ///       ，       ，      
}a[maxn];
bool cmp(node x,node y){
    if(x.st!=y.st) return x.st<y.st;
    else return x.ed<y.ed;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].st,&a[i].ed);
        a[i].num=a[i].ed-a[i].st+1;

    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) b[i]=a[i].num,c[i]=1;
    int max1=-1,max2=-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j].ed==a[i].st&&b[j]+a[i].num-1>=b[i])
            {
                b[i]=b[j]+a[i].num-1;
                c[i]=c[j]+1;
            }
        }
        max1=max(max1,b[i]); ///           
    }
    for(int i=1;i<=n;i++)///             
    {
        if(max1==b[i]) max2=max(max2,c[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]==max1&&max2==c[i])
        {
            cout << b[i] << " " << c[i];
            break;
        }
    }
    return 0;
}

后半部分のコードは少し复雑で、とても理解しやすい~~星光は道を急ぐ人を问わず、时間は心を负わない~