CodeForcesGym 100517I IQ Test

IQ Test

Time Limit: 2000ms

Memory Limit: 262144KB

This problem will be judged on CodeForcesGym. Original ID: 100517I
64-bit integer IO format: %I64d Java class name: (Any)

解题：动态规划

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 10010;
 5 int p[maxn],n;
 6 struct A {
 7     int val,id;
 8     bool operator<(const A &rhs) const {
 9         return val < rhs.val;
10     }
11 } a[maxn];
12 LL dp[maxn];
13 vector<int>ans[maxn];
14 int main() {
15 #define NAME "iq"
16     freopen(NAME".in","r",stdin);
17     freopen(NAME".out","w",stdout);
18     while(scanf("%d",&n),n) {
19         for(int i = 1; i <= n; ++i) {
20             scanf("%d",&a[i].val);
21             a[i].id = i;
22         }
23         sort(a + 1,a + n + 1);
24         memset(dp,0x3f,sizeof dp);
25         dp[0] = 0;
26         p[0] = -1;
27         for(int i = 0; i < maxn; ++i) ans[i].clear();
28         for(int i = 1; i <= n; ++i) {
29             for(int j = 0; j < i; ++j) {
30                 LL tmp = dp[j] + (LL)a[i].val*(n - j);
31                 if(tmp < dp[i]) {
32                     dp[i] = tmp;
33                     p[i] = j;
34                 }
35             }
36         }
37         printf("%I64d
",dp[n]);
38         int group = 0;
39         for(int i = p[n]; ~i; i = p[i]) ++ group;
40         printf("%d
",group);
41         int cur = n,cnt = group;
42         while(~p[cur]) {
43             for(int i = cur; i > p[cur]; --i) ans[cnt].push_back(a[i].id);
44             cur = p[cur];
45             --cnt;
46         }
47         for(int i = 1; i <= group; ++i) {
48             printf("%d",ans[i].size());
49             for(auto &it:ans[i]) printf(" %d",it);
50             putchar('
');
51         }
52     }
53     return 0;
54 }

View Code