动态规划，就是这样！ 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.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3QgdGhhdCB3aWxsIGJlIG9uIHRoZSA8ZW0+aTwvZW0+LXRoCiBwbGFjZSBpZiB3ZSBhcnJhbmdlIGFsbCB0aGUgc3RvbmUgY29zdHMgaW4gbm9uLWRlY3JlYXNpbmcgb3JkZXIpLiBUaGlzIHRpbWUgc2hlIHdpbGwgdGVsbCB5b3UgdHdvIG51bWJlcnMsIDxlbT5sPC9lbT4gYW5kIDxlbT5yPC9lbT4gKDE/odw/PGVtPmw8L2VtPj+h3D88ZW0+cjwvZW0+P6HcPzxlbT5uPC9lbT4pLAogYW5kIHlvdSBzaG91bGQgdGVsbCBoZXIgPGltZyBhbGlnbj0="middle" class="tex-formula" src="https://www.cppentry.com/upload_files/article/49/1_8wder__.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就讲吧，谢谢；