POJ1260-Pearls

전재 출처: 유유  http://user.qzone.qq.com/289065406/blog/1300164274
대체로 제목:
몇 가지 진주 와 그들의 단 가 를 제시 하고 최소한 의 돈 으로 같은 수량의 같은 (또는 더 높 은) 품질의 진 주 를 살 수 있 도록 요구한다.
[어떤 종류의 진주 n 개 (가격 은 p) 를 살 때 (n + 10) * p 의 돈 을 지불해 야 한다 고 규정 하고 있 습 니 다. 즉, 10 * p 를 추가 로 지불해 야 합 니 다.]
 
예 를 들 어 샘플 Input 의 두 번 째 예:
3
1 10
1 11
100 12
1 종 1 개, 2 종 1 개, 3 종 100 개 를 사 야 합 니 다.
일반 결제 (1 + 10) * 10 + (1 + 10) * 11 + (100 + 10) * 12 = 1551 원 (펄 102 개 구입)
그러나 모두 세 번 째 진주 의 가격 으로 지불 하면 102 개 를 살 수 있 고 그 중에서 전체적인 품질 도 향상 되 었 으 나 가격 은 떨 어 졌 다. (102 + 10) * 12 = 1344 위안 이다.
 
샘플 Input 의 첫 번 째 예:
2
100 1
100 2
통상 적 으로 (100 + 10) * 1 + (100 + 10) * 2 = 330 원 으로 지급
그러나 모두 두 번 째 진주 의 가격 으로 지불 하고 똑 같이 200 개 를 샀 습 니 다. 전체적인 품질 이 향상 되 었 지만 가격 도 올 랐 습 니 다. (202 + 10) * 2 = 424 원 입 니 다.
 
본 문제 의 관건 은:
（1）       사 달라 고 하 는 진주 의 수량 은 일정 합 니 다.
（2）       구입 한 진주 의 품질 은 향상 시 킬 수 있 으 나 떨 어 지 는 것 은 허용 되 지 않 는 다 (즉, 고 품질 진주 로 저 품질 을 대체 할 수 있다).
（3）       입력 시, 입력 한 진주 가격 은 반드시 앞에서 입력 한 것 보다 비 쌉 니 다.
（4）       (2) (3) 에서 알 수 있 듯 이 진주 의 대 체 는 연속 적 이 어야 하 며 점프 로 대체 할 수 없다. (이것 은 i + 2 류 로 i 류 진 주 를 대체 하면 최종 지불 가격 이 낮 아 지기 때문에 i + 1 류 로 i 류 진 주 를 대체 하면 최종 지불 가격 이 더욱 낮 아진 다 는 것 을 증명 하기 어렵 지 않다.)
 
이 네 가지 구속 조건 에 따라 진 주 를 구 매 하 는 방안 은 다음 과 같다.
진주 유형의 총 구간 [1, c] 에서 여러 개의 키 구간 을 나 누 는데 그 중에서 폐 구간 i1 ~ j1 의 진 주 는 모두 제1 류 진주 의 가격 p1 로 지불 하고 폐 구간 i2 ~ j2 의 진 주 는 모두 제2 류 진주 의 가격 p2 로 지불 하 며... 폐 구간 in ~ jn 의 진 주 는 모두 제 jn 류 진주 의 가격 pn 으로 지불한다.이 구간 들 은 서로 교차 하지 않 는 다.
나머지 진 주 는 원가 로 지불한다.
최종 지불 가격 이 가장 낮 을 수 있 도록 가장 좋 은 구분 방안 을 찾 아야 한다.
 
dp [i] 는 제 i 류 진 주 를 알 고 있 을 때 지불해 야 할 최저 가격 을 표시 합 니 다.
상태 방정식 은 다음 과 같다.
dp[i]=(a[i]+10)*p[i]+dp[i-1];  //제 i 종 진주 가 나 타 났 을 때 가격 을 최적화 하지 않 은 경우
dp[i]=min(dp[i],(sum[i]-sum[j]+10)*p[i]+dp[j]);  //매 거 j, 가격 최적화
 
dp[0]=0;  //Dp 초기 화

 1 //Memory Time 
 2 //220K   0MS 
 3 
 4 #include<iostream>
 5 using namespace std;
 6 
 7 int min(int a,int b)
 8 {
 9     return a<b?a:b;
10 }
11 
12 int main(int i,int j)
13 {
14     int test;
15     cin>>test;
16     while(test--)
17     {
18         /*Input & Initial*/
19 
20         int c;
21         cin>>c;
22 
23         int* a=new int[c+1];  //      
24         int* p=new int[c+1];  //      
25         int* dp=new int[c+1]; //dp[i]      i    ,         
26         int* sum=new int[c+1];//sum[i]=∑a[i]
27 
28         sum[0]=0;
29         for(i=1;i<=c;i++)
30         {
31             cin>>a[i]>>p[i];
32             sum[i]=sum[i-1]+a[i];
33         }
34 
35         /*Dp*/
36 
37         dp[0]=0;  //Dp   
38         for(i=1;i<=c;i++)
39         {
40             dp[i]=(a[i]+10)*p[i]+dp[i-1];   //  i      ，        
41             for(j=0;j<i;j++)  //   i          ，      
42                 dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*p[i]);  //  dp[i] ，     j<i，dp[j]       
43         }                                                        //(sum[i]-sum[j]+10)*p[i]  j+1~i     i         
44         cout<<dp[c]<<endl;
45 
46         delete a,p,dp,sum;
47     }
48     return 0;
49 }