動態規劃，就是這樣！ CodeForces 433B - Kuriyama Mirai's Stones

Kuriyama Mirai has killed many monsters and got many (namely n) stones. She numbers the stones from 1 to n. The cost of the i-th stone is vi. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions:

1. She will tell you two numbers, l and r (1?≤?l?≤?r?≤?n), and you should tell her .
2. Let ui be the cost of the i-th cheapest stone (the cZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3QgdGhhdCB3aWxsIGJlIG9uIHRoZSA8ZW0+aTwvZW0+LXRoCiBwbGFjZSBpZiB3ZSBhcnJhbmdlIGFsbCB0aGUgc3RvbmUgY29zdHMgaW4gbm9uLWRlY3JlYXNpbmcgb3JkZXIpLiBUaGlzIHRpbWUgc2hlIHdpbGwgdGVsbCB5b3UgdHdvIG51bWJlcnMsIDxlbT5sPC9lbT4gYW5kIDxlbT5yPC9lbT4gKDE/odw/PGVtPmw8L2VtPj+h3D88ZW0+cjwvZW0+P6HcPzxlbT5uPC9lbT4pLAogYW5kIHlvdSBzaG91bGQgdGVsbCBoZXIgPGltZyBhbGlnbj0="middle" class="tex-formula" src="http://www.bkjia.com/uploads/allimg/140527/004Z0N13-1.png" alt="\">.

   For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy.

   Input

   The first line contains an integer n (1?≤?n?≤?105). The second line contains n integers: v1,?v2,?...,?vn (1?≤?vi?≤?109) — costs of the stones.

   The third line contains an integer m (1?≤?m?≤?105) — the number of Kuriyama Mirai's questions. Then follow m lines, each line contains three integers type, l and r (1?≤?l?≤?r?≤?n; 1?≤?type?≤?2), describing a question. If type equal to 1, then you should output the answer for the first question, else you should output the answer for the second one.

   Output

   Print m lines. Each line must contain an integer — the answer to Kuriyama Mirai's question. Print the answers to the questions in the order of input.

   Sample test(s) input

   6
   6 4 2 7 2 7
   3
   2 3 6
   1 3 4
   1 1 6
   

   output

   24
   9
   28
   

   input

   4
   5 5 2 3
   10
   1 2 4
   2 1 4
   1 1 1
   2 1 4
   2 1 2
   1 1 1
   1 3 3
   1 1 3
   1 4 4
   1 2 2
   

   output

   10
   15
   5
   15
   5
   5
   2
   12
   3
   5
   

   Note

   Please note that the answers to the questions may overflow 32-bit integer type.

   題目說給一串數字，然後給指令1或2，輸入l，r求第l到r的和，講詳細點：先輸入一個n，代表有多少個元素，然後輸入n個元素，然後輸入一個q代表有多少次指令，1的指令就是直接將a[l]一直加加到a[r]，然後輸出和，2的指令是先將a[]排序，sort就行了，然後和上面一樣求和，思路很簡單，哈哈，看到這樣的B題很開心吧，普通寫法for循環一個個加的話，寫完你就發現TLE了，而且TLE的很開心啊！！！！！！ 都說了這是動態規劃啊！！！！！！ 咱們這樣存儲：每個元素存儲的是前i個元素的和，這樣a[l]一直到a[r]的表達式就為a[r]-a[l-1]; 好好理解下，對吧？！ 動態規劃就是拿空間換時間的算法，在運行過程中會產生大量中間數據進行抉擇，每一個狀態始終影響下一步的狀態！！！！！！ 嗯，貼代碼時間：

   #include
   #include
   #include
   #include
   using namespace std;
   #define maxn 100006
   __int64 sum;
   __int64 pp[maxn]={0},p[maxn]={0},liu[maxn],xp[maxn];
   int main()
   {
       int i,j,k;
       int t,n,m;
       int l,r;
       while(scanf("%d",&n)!=EOF)
       {
           p[0]=0;
           for(i=1;i<=n;i++)
           {
               scanf("%I64d",&liu[i]);
               xp[i]=liu[i];
               p[i]=p[i-1]+liu[i];
           }
           xp[0]=0;
           sort(xp,xp+n+1);
           for(i=1;i<=n;i++)
               pp[i]=pp[i-1]+xp[i];
           scanf("%d",&t);
           while(t--)
           {
               scanf("%d",&m);
               if(m==1)
               {
                   scanf("%d%d",&l,&r);
                   sum=p[r]-p[l-1];
                   printf("%I64d\n",sum);
               }
               else if(m==2)
               {
                   scanf("%d%d",&l,&r);
                   sum=pp[r]-pp[l-1];
                   printf("%I64d\n",sum);
               }
           }
       }
       return 0;
   }

   看出bug就講吧，謝謝；