NOIP 2005解題報告(川を渡る)

2.川を渡る(river.pas/c/cpp)【問題の説明】川には丸木橋があり、1匹のカエルが丸木橋に沿って川の片側から反対側に飛びたいと思っています.橋の上には石がいくつかあります.カエルはこれらの石を踏むのが嫌いです.橋の長さとカエルが一度に飛び越える距離は正の整数なので、丸木橋のカエルが着く可能性がある点を数軸上の整点:0,1,...,L(ここで、Lは橋の長さである).座標が0の点は橋の起点を表し、座標がLの点は橋の終点を表す.カエルは橋の起点から、終点方向にジャンプし続ける.一回のジャンプの距離はSからTまでの任意の正の整数である(S,Tを含む).カエルが座標Lの点にジャンプしたりスキップしたりした場合、カエルが独木橋から飛び出したとしても.タイトルは独木橋の長さL、カエルがジャンプする距離範囲S,T、橋の石の位置を示します.カエルが川を渡るには、少なくとも踏む必要がある石の数を決定するのが任務です.【入力ファイル】入力ファイルriver.inの最初の行には正の整数Lがあります(1<=L<=10^9)は、独木橋の長さを表す.2行目には、カエルが一度にジャンプする最小距離、最大距離、および橋の上の石の個数の3つの正の整数S,T,Mがあり、そのうち1<=S<=10,1<=M<=100である.3行目には、M個の異なる正の整数がそれぞれこのM個の石の数軸上の位置を表す(データ保証橋の始点と終点に石はありません).隣接するすべての整数の間を1つのスペースで区切っています.【出力ファイル】出力ファイルriver.outには、カエルが川を渡るのに最低限必要な石の数を示す整数が1つしか含まれていません.【データ規模】30%のデータに対して、L<=10000;すべてのデータに対して、L<=10^9です.【問題解決報告】最も簡単なDP方式は考えにくいが、Lの長さが10の9の方であれば、そのままDPを見て終わりとなる.しかし、Lがどんなに大きくても、石の個数は100以内であることがわかるので、経路圧縮が可能といえる.どのように押すかについては、100 100で押すこともできるし、tの値によって押すこともできる(実はあまりきつく押さなくてもよい).
コードは次のとおりです.

#include
#include
using namespace std;

int L,k;  
int S,T,M,i,j,min;  
long stone[102],b[10005];  
int Num[10005]; 
int X[120];

int main()  
{  
    freopen("river.in","r",stdin);
    freopen("river.out","w",stdout);
    memset(Num,-1,sizeof(Num));  
    memset(b,0,sizeof(b));  
    scanf("%d",&L);  
    scanf("%d%d%d",&S,&T,&M);
    for (i=0;iscanf("%d",&stone[i]);
    if(S==T)
    {  
        min = 0;  
        for (i=0;iif (stone[i] % S == 0)  
                min++;  
        }  
        printf("%d",min);  
        return 0;
    }  
    for (i=0;i1;i++)  
    {  
        for (j=0;j1;j++)  
            if(stone[j]>stone[j+1])  
            {  
                int temp;
                temp = stone[j];  
                stone[j]=stone[j+1];  
                stone[j+1]=temp;  
            }  
    }  
    stone[M]=L; 

    for(i=0;i1]-stone[i]; 

    if (stone[0]>90)  
    {  
        k = stone[0]-90;  
        for(i=0;i<=M;i++)  
        stone[i] -= k;  
    }  
    for (i=1;i<=M;i++)  
    {  
        if (stone[i]-stone[i-1]>90)  
        {  
            k = stone[i]-stone[i-1]-90;  
            for(j=i;j<=M;j++)  
            stone[j] -= k;  
        }  
    }   

    for (i=0;i1;  
    Num[0]=0;  
    for (i=S;i101;  
        for (j=i-T;j<=i-S;j++)  
        {  
            if (Num[j]1&&j>=0)  
            min=Num[j];  
        }  
        if (min!=101)  
        Num[i]=min+b[i];  
    }  
    min=101;  
    for (i=stone[M];iif (Num[i]1)  min = Num[i];  
    }  
    printf("%d",min);    
    return 0;  
}  

3.篝火パーティー(fire.pas/c/cpp)【問題説明】佳佳は高校に入ったばかりで、軍事訓練の時、佳佳は苦労に耐え、すぐに教官に認められ、「小教官」になった..軍事訓練が終わった夜、佳佳は同級生たちに焚き火パーティーを組織するように命令された.全部でn人の同級生がいて、番号は1からnまでです.最初は、学生たちは1、2、......、nの順番で1周していましたが、実際には誰もが一番隣の学生を望んでいました.どのように命令を下して同級生の順序を調整して、新しい輪を形成して、同級生たちの願望に合致させて、佳佳の前に置く一大難題になります.佳佳は同級生たちに命令を下すことができ、それぞれの命令の形式は以下の通りである:(b 1,b 2,...bm-1,bm)ここでmの値は佳佳によって決定され、命令mの値は毎回異なることができる.このコマンドの役割は、(b 1,b 2,...bm-1,bm)のこのm人の同級生の位置を移動することです.b 1をb 2の位置に、b 2をb 3の位置に、・・・、bmをb 1の位置に、と要求する.各コマンドを実行するには、いくつかの代価が必要です.命令がm個人の位置を移動する場合、この命令の代価はmであると仮定する.私たちは佳佳が最小限の総代価で同級生たちの意思を実現する必要があります.あなたは佳佳を助けることができますか?【入力ファイル】入力ファイルfire.inの最初の行は整数nである(3<=n<=50000)は、合計n人の同級生がいることを示す.その後、n行の各行には2つの異なる正の整数が含まれ、1のスペースで区切られ、それぞれ番号が1の同級生が最も隣接したい2人の同級生の番号を表し、番号は2の同級生が最も隣接したい2人の同級生の番号である......、番号はnの同級生が最も隣接したい2人の同級生の番号である.【出力ファイル】出力ファイルfire.outは1行を含み、この行には整数が1つしか含まれず、最小の総代価となる.どのように調整しても学生一人一人の願いに合わない場合は、-1を出力する.【問題解決レポート】