[二分查找]NOIP2011提高組：聰明的質檢員 qc 解題報告

【問題描述】

試題檢視：GoogleDocs

小 T 是一名質量監督員，最近負責檢驗一批礦產的質量。這批礦產共有 n 個礦石，從 1 到 n 逐一編號，每個礦石都有自己的重量 wi 以及價值 vi。檢驗礦產的流程是：

1、給定 m個區間[Li，Ri]；

2、選出一個參數 W；

3、對於一個區間[Li，Ri]，計算礦石在這個區間上的檢驗值 Yi ： 

若這批礦產的檢驗結果與所給標準值 S 相差太多，就需要再去檢驗另一批礦產。小 T 不想費時間去檢驗另一批礦產，所以他想通過調整參數 W 的值，讓檢驗結果儘可能的靠近標準值 S，即使得 S-Y的絕對值最小。請你幫忙求出這個最小值。

【輸入】

輸入文件 qc.in。

第一行包含三個整數n，m，S，分別表示礦石的個數、區間的個數和標準值。

接下來的n 行，每行2 個整數，中間用空格隔開，第i+1 行表示i 號礦石的重量wi 和價值vi 。

接下來的m 行，表示區間，每行2 個整數，中間用空格隔開，第i+n+1 行表示區間[Li,Ri]的兩個端點Li 和Ri。注意：不同區間可能重合或相互重疊。

【輸出】

輸出文件名爲qc.out。

輸出只有一行，包含一個整數，表示所求的最小值。

【輸入輸出樣例】

qc.in

5 3 15

1 5

2 5

3 5

4 5

5 5

1 5

2 4

3 3

qc.out

10

【輸入輸出樣例說明】

當W 選4 的時候，三個區間上檢驗值分別爲20、5、0，這批礦產的檢驗結果爲25，此時與標準值S 相差最小爲10。

【數據範圍】

對於10%的數據，有1≤n，m≤10；

對於30%的數據，有1≤n，m≤500；

對於50%的數據，有1≤n，m≤5,000；

對於70%的數據，有1≤n，m≤10,000；

對於100%的數據，有1≤n，m≤200,000，0 < wi, vi≤10^6，0 < S≤10^12，1≤Li≤Ri≤n。

 【分析】

本題的正解是二分W，從0～MaxW+1二分。計算Y時要先預處理，把所有大於W的礦石記錄下來，然後再計算每個區間的值。

二分結束後，找出Min{Get(Right)，Get(Left)}輸出即可。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int N,M;
long long S;
const int MAXN=200001;
int W[MAXN];
int V[MAXN];
int L[MAXN];
int Sum[MAXN];
int R[MAXN];
long long TV[MAXN];
int TN[MAXN];
  
void init()
{
    Sum[0]=0;
    cin>>N>>M>>S;
    for (int i=1;i<=N;i++)
    {
        cin>>W[i]>>V[i];
        Sum[i-1]=W[i];
    }
    for (int i=1;i<=M;i++)
        cin>>L[i]>>R[i];
    sort(Sum,Sum+N);
    Sum[N]=Sum[N-1]+1;
}

long long Get(int w)
{
    long long res=0;
    TV[0]=0;
    TN[0]=0;
    for (int i=1;i<=N;i++)
    {
        if(W[i]>=w)
        {
            TV[i]=TV[i-1]+V[i];
            TN[i]=TN[i-1]+1;
            continue;
        }
        else
        {
            TV[i]=TV[i-1];
            TN[i]=TN[i-1];
        }
    }
  
    for (int i=1;i<=M;i++)
    {
        int tl=L[i];
        int tr=R[i];
        long long Temp=(TN[tr]-TN[tl-1])*(TV[tr]-TV[tl-1]);
        res+=Temp;
    }
  
    return res;
}

long long Abs(long long t)
{
    if(t>0)
        return t;
    else
        return -t;
}

void dichotomy()
{
    int Right;
    int Left;
    for (Left=0,Right=N;Left+1<Right;)
    {
        long long Temp=Get(Sum[(Right+Left)/2]);
        if(Temp>=S)
            Left=(Left+Right)/2;
        else
            Right=(Left+Right)/2;
    }
  
    long long TW1,TW2;
    TW1=Abs(Get(Sum[Right])-S);
    TW2=Abs(Get(Sum[Left])-S);
    if(TW2<TW1)
    {
        TW1=TW2;
    }
    cout<<TW1<<endl;
}  

int main()
{
    freopen("qc.in","r",stdin);
    freopen("qc.out","w",stdout);
    init();
    dichotomy();
    return 0;
}

動態規劃練習題：填加號 解題報告

【問題描述】
有一個由數字 1 ， 2 ， … ， 9 組成的數字串（長度不超過 200 ），問如何將 M(M<=20) 個加號 (“+”) 插入到這個數字串中，使所形成的算術表達式的值最小。請編一個程序解決這個問題。 注意： 加號不能加在數字串的最前面或最末尾，也不應有兩個或兩個以上的加號相鄰。 M 保證小於數字串的長度。 例如：數字串 79846 ，若需要加入兩個加號，則最佳方案為 79+8+46 ，算術表達式的值 133 。
【輸入格式】
數字串在輸入文件的第一行行首（數字串中間無空格且不折行），Ｍ的值在輸入文件的第二行行首。
【輸出格式】
輸出所求得的最小和的精確值。
【輸入輸出樣例】

輸入：
exam4.in
82363983742
3
輸出：
exam4.out
2170

【分析】
動態規劃，類似於『NOIP2000 乘積最大』。
狀態設定：
F[i,j] ：前i個數添加j個乘號的最小和
Num[i,j]：原數中第i個數到第j個數組成的新數。
邊界狀態：F[i,0]=Num[1,i]
狀態轉移方程： F[i,j]=Min{F[k,j-1]+Num[k+1,i]}
目標狀態：F[N,K]
由於數據比較大，所以需要高精度計算。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int SIZE=201;
int K;
int N;
typedef unsigned short int usint;
struct hugeint
{
 usint len,num[SIZE];
};
hugeint Num[201][201];
hugeint F[201][21];
void print(hugeint a)
{
 int i;
 for (i=a.len;i>=1;i--)
  printf("%d",a.num[i]);
 printf("\n");
}
hugeint add(hugeint a,hugeint b)
{
 int i;
 hugeint ans;
 memset(ans.num,0,sizeof(ans.num));
 if (a.len>b.len)
  ans.len=a.len;
 else
  ans.len=b.len;
 for (i=1;i<=ans.len;i++)
 {
  ans.num[i]+=(a.num[i]+b.num[i]);
  ans.num[i+1]+=ans.num[i]/10;
  ans.num[i]%=10;
 }
 if (ans.num[ans.len+1]>0)
  ans.len++;
 return ans;
}
bool over(hugeint a,hugeint b)
{
 int i;
 if (a.len<b.len)
  return false;
 if (a.len>b.len)
  return true;
 for (i=a.len;i>=1;i--)
 {
  if (a.num[i]<b.num[i])
   return false;
  if (a.num[i]>b.num[i])
   return true;
 }
 return false;
}
void init()
{
 hugeint tmp;
 memset(tmp.num,0,sizeof(tmp.num));
 char str[201];
 scanf("%s\n%d\n",&str,&K);
 int len=strlen(str);
 tmp.len=len;
 N=len;
 for (int i=0;i<len;i++)
 {
  tmp.num[i+1]=str[i]-'0';
 }
 for (int i=1;i<=len;i++)
 {
  for (int j=i;j<=len;j++)
  {
   memset(Num[i][j].num,0,sizeof(Num[i][j].num));
   Num[i][j].len=j-i+1;
   int top=Num[i][j].len;
   for (int k=i;k<=j;k++)
   {
    Num[i][j].num[top]=tmp.num[k];
    top--;
   }
   /*
   printf("%d %d %d ",i,j,Num[i][j].len);
   print(Num[i][j]);
   */
  }
 }
}
void dynamic()
{
 for (int i=1;i<=N;i++)
  F[i][0]=Num[1][i];
 for (int j=1;j<=K;j++)
 {
  for (int i=1;i<=N;i++)
  {
   for (int k=1;k<=N;k++)
    F[i][j].num[k]=9;
   F[i][j].len=N;
   for (int k=1;k<=i-1;k++)
   {
    hugeint temp=add(F[k][j-1],Num[k+1][i]);
    if(over(F[i][j],temp) )
    {
     F[i][j]=temp;
    }
   }
  }
 }
 print(F[N][K]);
}
int main()
{
 freopen("exam4.in","r",stdin);
 freopen("exam4.out","w",stdout);
 init();
 dynamic();
 return 0;
}

[動態規劃]OI練習題：乘法問題 [chf] 解題報告

【問題描述】
設有一個長度為 N 的數字字元串，分成 K+1 個部分，使得 K+1 個部 分的乘積最大。 例如 N=6 ，且數字字元串為 ‘ 310143 ‘ ， K=3. 此時可能有的情況有以 下各種：
3 ＊ 1 ＊ 0 ＊ 143=0
3 ＊ 1 ＊ 01 ＊ 43=129
3 ＊ 1 ＊ 014 ＊ 3=126
3 ＊ 10 ＊ 1 ＊ 43=1290
3 ＊ 10 ＊ 14 ＊ 3=1260
3 ＊ 101 ＊ 4 ＊ 3=3636
31 ＊ 0 ＊ 1 ＊ 43=0
31 ＊ 01 ＊ 4 ＊ 3=372
310 ＊ 1 ＊ 4 ＊ 3=3720
問題：當 N ，數字串， K 給出之後，找出一種分法使其乘積最大。
【輸入格式】
輸入由兩行組成，第一行有兩個整數，n（1≤n≤30）、k（1≤n≤30）；n表示數字串長度、k表示乘號

個數。第二行是數字串。
【輸出格式】
輸出為一個整數，為乘積最大值。
【輸入樣例】
輸入文件名：chf.in
9 4
321044105
輸出文件名：chf.out
5166000
【分析】
動態規劃，和『NOIP2001 乘積最大』一樣。
狀態設定：
F[i,j]：前i個數字添加j個乘號時的最大值。
Num[i,j]：第i的數到第j個的數組成的數，可以在DP前用一個O(N^2)的預處理求出。
狀態轉移方程：
F[i,j]=Max(F[k,j-1]*Num[k+1][i])  (1<=k<=i-1)
目標狀態：  F[N,K]
時間複雜度：O(2*N^2)

【我的代碼】

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; typedef long long LL; LL N,K; LL num[100][100]; LL F[100][100];   LL Max(LL a,LL b) { if (a>=b) return a; return b; }   LL myatoi(char *str) { LL ret=0; LL sign=1; if(*str=='-') sign=-1; else ret=ret*10+(*str-'0'); str++;   while(*str!= '\0') { ret=ret*10+(*str-'0'); str++; } return sign*ret; }   void init() { cin>>N>>K; char Temp[100]; cin>>Temp; char tmp[100]; for (unsigned int i=1;i<=strlen(Temp);i++) { for (unsigned int j=i;j<=strlen(Temp);j++) { unsigned int ti=i-1; unsigned int tj=j-1; memset(tmp,'\0',sizeof(tmp)); for (unsigned int k=ti;k<=tj;k++) tmp[k-ti]=Temp[k]; num[i][j]=myatoi(tmp); } } }   void dp() { for (int i=1;i<=N;i++) F[i][0]=num[1][i]; for (int j=1;j<=K;j++) { for (int i=1;i<=N;i++) { F[i][j]=0; for (int k=1;k<=i-1;k++) F[i][j]=Max(F[i][j],F[k][j-1]*num[k+1][i]); } } cout<<F[N][K]<<endl; }   int main() { freopen("chf.in","r",stdin); freopen("chf.out","w",stdout); init(); dp(); return 0; }