1001         KK的GFriend

本题水题。遍历输入数据给出的字符串。如果出现的I LOVE U各个字符都至少都有m个的话，则满足要求，否则不满足。

之前比赛时，输出描述的字符串和Sample Output不符（Sample Output为正确答案），导致部分同学wrong answer，请见谅。

[cpp]
view plaincopyprint?

1. #include<iostream>
     
2. #include<cstring>
     
3. #include<string>
     
4. #include<cstdio>
     
5. using namespace std;  
6. const int maxn=10001;  
7. char inp[maxn];  
8. int num[6];  
9. int main()  
10. {  
11.     int cas,n,m;  
12.     scanf("%d",&cas);  
13.     while(cas--)  
14.     {  
15.         memset(num,0,sizeof(num));  
16.         scanf("%d%d",&n,&m);  
17.         for(int i=1; i<=n; i++)  
18.         {  
19.             scanf("%s",&inp);  
20.             for(int i=0; i<strlen(inp); i++)  
21.             {  
22.                 switch(inp[i])  
23.                 {  
24.                     case 'I':num[0]++;break;  
25.                     case 'L':num[1]++;break;  
26.                     case 'O':num[2]++;break;  
27.                     case 'V':num[3]++;break;  
28.                     case 'E':num[4]++;break;  
29.                     case 'U':num[5]++;break;  
30.                 }  
31.             }  
32.         }  
33.         int res=maxn;  
34.         for(int i=0; i<6; i++)  
35.             res=min(res,num[i]);  
36.         if(res>=m) printf("KK will have a girlfriend!\n");  
37.         else  printf("KK can only have gay friend~\n");  
38.   
39.     }  
40.     return 0;  
41. }  

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int maxn=10001;
char inp[maxn];
int num[6];
int main()
{
    int cas,n,m;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(num,0,sizeof(num));
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%s",&inp);
            for(int i=0; i<strlen(inp); i++)
            {
                switch(inp[i])
                {
                    case 'I':num[0]++;break;
                    case 'L':num[1]++;break;
                    case 'O':num[2]++;break;
                    case 'V':num[3]++;break;
                    case 'E':num[4]++;break;
                    case 'U':num[5]++;break;
                }
            }
        }
        int res=maxn;
        for(int i=0; i<6; i++)
            res=min(res,num[i]);
        if(res>=m) printf("KK will have a girlfriend!\n");
        else  printf("KK can only have gay friend~\n");

    }
    return 0;
}

1002         炮打学弟

这题是一道简单题，主要是要考虑的情况稍多，如果都考虑到了就没有什么了。

需要注意的地方：

1. x2<x1 输出 Xue di so diao can fly

2. x2=x1时

（1）y=0 输出0.00

（2）y!=0&&vx>0 输出 Xue di so diao can fly

3. x2>x1&&vx=0输出 Xue di so diao can fly

其他情况常规的算一下就可以了。

标准程序：

[cpp]
view plaincopyprint?

1. #include<iostream>
     
2. #include<cstdio>
     
3. #include<cstring>
     
4. #include<string>
     
5. #include<set>
     
6. #include<vector>
     
7. #include<queue>
     
8. #include<map>
     
9. #include<algorithm>
     
10. #include<cmath>
      
11. #include<stdlib.h>
      
12. #include<time.h>
      
13. using namespace std;  
14. #define mmax 100000+100
      
15. int main(){  
16.     int x1,x2,y,vx;  
17.     double vy,g=9.8;  
18.     int t;  
19.     cin>>t;  
20.     //freopen("I:\\input.txt","r",stdin);
      
21.     //freopen("I:\\ouput.txt","w",stdout);
      
22.     while(t--){  
23.         cin>>x1>>x2>>y>>vx;  
24.         if(x1>x2){  
25.             cout<<"Xue di so diao can fly"<<endl;  
26.             continue;  
27.         }  
28.         if(x1==x2){  
29.             if(y==0){  
30.                 printf("%.2f\n",0.00);  
31.                 continue;  
32.             }  
33.             else if(vx>0)  cout<<"Xue di so diao can fly"<<endl;  
34.             else{  
35.                 double t=sqrt(2*y/g);  
36.                 printf("%.2f\n",g*t);  
37.             }  
38.             continue;  
39.         }  
40.         else{  
41.             if(vx==0){  
42.                 cout<<"Xue di so diao can fly"<<endl;  
43.                 continue;  
44.             }  
45.             else{  
46.                 double t=(x2-x1)*1.0/vx;  
47.                 vy=(0.5*g*t*t+y)/t;  
48.                 printf("%.2f\n",vy);  
49.             }  
50.         }  
51.     }  
52. }  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define mmax 100000+100
int main(){
    int x1,x2,y,vx;
    double vy,g=9.8;
    int t;
    cin>>t;
    //freopen("I:\\input.txt","r",stdin);
    //freopen("I:\\ouput.txt","w",stdout);
    while(t--){
        cin>>x1>>x2>>y>>vx;
        if(x1>x2){
            cout<<"Xue di so diao can fly"<<endl;
            continue;
        }
        if(x1==x2){
            if(y==0){
                printf("%.2f\n",0.00);
                continue;
            }
            else if(vx>0)  cout<<"Xue di so diao can fly"<<endl;
            else{
                double t=sqrt(2*y/g);
                printf("%.2f\n",g*t);
            }
            continue;
        }
        else{
            if(vx==0){
                cout<<"Xue di so diao can fly"<<endl;
                continue;
            }
            else{
                double t=(x2-x1)*1.0/vx;
                vy=(0.5*g*t*t+y)/t;
                printf("%.2f\n",vy);
            }
        }
    }
}

1003         区间平均值

这题是水题，直接暴力求平均值即可。

1004         饿了么

这题是水题，直接排个序就好了，1000的数据量，用冒泡排序都可以。

1005         分辨机器人

m<=15  2^15==32768 所以可以直接暴力解决。但是由于开始数据出问题了，导致很多同学wa了，实在抱歉，想知道自己算法是否OK的同学可以到赛后（http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1005&cid=25698&problem=Problem%20%20E）提交。

标准程序：

[cpp]
view plaincopyprint?

1. #include <iostream>
     
2. #include <algorithm>
     
3. #include <cstring>
     
4. #include <string>
     
5. #include <cstdio>
     
6. #include <queue>
     
7. #include <cmath>
     
8. #include <vector>
     
9. #include <set>
     
10. #include <bitset>
      
11. #include <map>
      
12. #define  pb push_back
      
13. #define  lson l,m,rt<<1
      
14. #define  rson m+1,r,rt<<1|1
      
15. typedef  long long LL;  
16. using namespace std;  
17. int s[105][20];  
18. int T,n,m,ans;  
19. int B[20];  
20. string ko;  
21. map<string,int>M;  
22. void dfs(int *B,int num)  
23. {  
24.     if(num==m)  
25.     {  
26.         M.clear();  
27.         for(int i=1;i<=n;i++)  
28.         {  
29.             ko = "";  
30.             for(int j=1;j<=m;j++)  
31.                 if(B[j]==1) ko += (s[i][j]+'0');  
32.             if(M[ko]) return ;  
33.             else M[ko] = 1;  
34.         }  
35.         int flag = 0;  
36.         for(int i=1;i<=m;i++) flag+=B[i];  
37.         if(ans>flag)  
38.             ans = flag;  
39.     }  
40.     else  
41.     {  
42.         B[num+1] = 0;  
43.         dfs(B,num+1);  
44.         B[num+1] = 1;  
45.         dfs(B,num+1);  
46.     }  
47. }  
48. void solve()  
49. {  
50.     ans = m;  
51.     B[0] = 0;  
52.     dfs(B,0);  
53.     printf("%d\n",ans);  
54. }  
55. int main()  
56. {  
57.     scanf("%d",&T);  
58.     while(T--)  
59.     {  
60.         memset(B,0,sizeof(B));  
61.         scanf("%d%d",&n,&m);  
62.         for(int i=1; i<=n; i++)  
63.             for(int j=1; j<=m; j++)  
64.             {  
65.                 scanf("%d",&s[i][j]);  
66.             }  
67.         solve();  
68.     }  
69.     return 0;  
70. }  

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#define  pb push_back
#define  lson l,m,rt<<1
#define  rson m+1,r,rt<<1|1
typedef  long long LL;
using namespace std;
int s[105][20];
int T,n,m,ans;
int B[20];
string ko;
map<string,int>M;
void dfs(int *B,int num)
{
    if(num==m)
    {
        M.clear();
        for(int i=1;i<=n;i++)
        {
            ko = "";
            for(int j=1;j<=m;j++)
                if(B[j]==1) ko += (s[i][j]+'0');
            if(M[ko]) return ;
            else M[ko] = 1;
        }
        int flag = 0;
        for(int i=1;i<=m;i++) flag+=B[i];
        if(ans>flag)
            ans = flag;
    }
    else
    {
        B[num+1] = 0;
        dfs(B,num+1);
        B[num+1] = 1;
        dfs(B,num+1);
    }
}
void solve()
{
    ans = m;
    B[0] = 0;
    dfs(B,0);
    printf("%d\n",ans);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(B,0,sizeof(B));
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                scanf("%d",&s[i][j]);
            }
        solve();
    }
    return 0;
}

1006         佳米的问题

这是一个想法题，首先我们需要找出最大的LCM(x,y).由于x+y==m&& x>=1 && y>=1 ,有一个很简单的数学依据，加入我们只是找(x*y)最大，那肯定( m/2*(m-m/2) )最大，因为这就是一个开口向下的二次函数曲线，而顶点就是(m/2)或者(m-m/2),但是我们要找的是x与y的最小公倍数，所以只需要从m/2开始向下枚举x，找到gcd(x,m-x)==1，此时LCM(x,y)最大。

然后就是如何用LCM(x,y)去填充数组使得最小的元素最大的问题了，那么这个其实有一个很简单的方法，直接二分答案即可。

标准程序：

[cpp]
view plaincopyprint?

1. #include <iostream>
     
2. #include <algorithm>
     
3. #include <cstring>
     
4. #include <string>
     
5. #include <cstdio>
     
6. #include <queue>
     
7. #include <cmath>
     
8. #include <vector>
     
9. #include <set>
     
10. #include <bitset>
      
11. #include <map>
      
12. #define  pb push_back
      
13. #define  lson l,m,rt<<1
      
14. #define  rson m+1,r,rt<<1|1
      
15. typedef  long long LL;  
16. using namespace std;  
17. LL gcd(LL a,LL b)  
18. {  
19.     return a==0?b:gcd(b%a,a);  
20. }  
21. const int maxn = 100010;  
22. LL s[maxn];  
23. LL T,n,num,m;  
24. bool solve(LL mid,LL num)  
25. {  
26.     LL ok = num;  
27.     for(int i=1;i<=n;i++)  
28.     {  
29.         if(s[i] < mid){  
30.             ok -= abs( mid - s[i] );  
31.         }  
32.         if(ok<0) break;  
33.     }  
34.     return ok>=0;  
35. }  
36. int main()  
37. {  
38.     #ifndef ONLINE_JUDGE
      
39.       freopen("in.txt","r",stdin);  
40.       freopen("out2.txt","w",stdout);  
41.     #endif ///ONLINE_JUDGE
      
42.     scanf("%I64d",&T);  
43.     while(T--){  
44.         scanf("%I64d",&n);  
45.         for(int i=1;i<=n;i++)  
46.         {  
47.             scanf("%I64d",&s[i]);  
48.         }  
49.         scanf("%I64d",&m);  
50.         for(LL i=m/2;i>=1;i--)  
51.         {  
52.             if(gcd(i,m-i)==1)  
53.             {  
54.                 num=i*(m-i);  
55.                 break;  
56.             }  
57.         }  
58.         LL l=-1*1e9,r = 1ll*1e16,mid,ans=-1*1e9;  
59.         while(l<=r)  
60.         {  
61.             mid = (l+r)/2;  
62.             if(solve(mid,num)){  
63.                 ans = max(ans,mid);  
64.                 l = mid + 1;  
65.             }  
66.             else r = mid - 1;  
67.         }  
68.         printf("%I64d\n",ans);  
69.     }  
70.     return 0;  
71. }  

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#define  pb push_back
#define  lson l,m,rt<<1
#define  rson m+1,r,rt<<1|1
typedef  long long LL;
using namespace std;
LL gcd(LL a,LL b)
{
    return a==0?b:gcd(b%a,a);
}
const int maxn = 100010;
LL s[maxn];
LL T,n,num,m;
bool solve(LL mid,LL num)
{
    LL ok = num;
    for(int i=1;i<=n;i++)
    {
        if(s[i] < mid){
            ok -= abs( mid - s[i] );
        }
        if(ok<0) break;
    }
    return ok>=0;
}
int main()
{
    #ifndef ONLINE_JUDGE
      freopen("in.txt","r",stdin);
      freopen("out2.txt","w",stdout);
    #endif ///ONLINE_JUDGE
    scanf("%I64d",&T);
    while(T--){
        scanf("%I64d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%I64d",&s[i]);
        }
        scanf("%I64d",&m);
        for(LL i=m/2;i>=1;i--)
        {
            if(gcd(i,m-i)==1)
            {
                num=i*(m-i);
                break;
            }
        }
        LL l=-1*1e9,r = 1ll*1e16,mid,ans=-1*1e9;
        while(l<=r)
        {
            mid = (l+r)/2;
            if(solve(mid,num)){
                ans = max(ans,mid);
                l = mid + 1;
            }
            else r = mid - 1;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

1007         Crisis

图论。本题可谓是排在难题位置的简单题。描述偏多，但是只要学习过最大流算法的同学应该都可以做出来。

N件武器，每件都可以选择特定的几个目标进行攻击。但是每件武器只允许攻击一次并只能造成1点伤害。因此，我们构建网络，将n件武器每件当作一个点，与源点相连，形成的边容量为1。再将m个目标当作n个点，若某一武器能够攻击到敌人，则将它们两个点相连，边容量为1。

又由于每个敌人的护盾有限。而被摧毁的战舰无法再被攻击，因此，将m个敌人分别与汇点相连，边容量为该敌人的护盾值。

至此，建模完毕。接下来只需要套用最大流算法，即可计算出最大攻击输出。

标准程序：

[cpp]
view plaincopyprint?

1. #include<iostream>
     
2. #include<cstdio>
     
3. #include<cstring>
     
4. #include<algorithm>
     
5. #include<vector>
     
6. #include<queue>
     
7. #define INF 0x7fffffff
     
8. using namespace std;  
9. const int maxn=1010;  
10. class Edge  
11. {  
12. public :  
13.     int from,to,cap,flow;  
14.     Edge(int fr,int t,int c,int fl)  
15.     {  
16.         from=fr;  
17.         to=t;  
18.         cap=c;  
19.         flow=fl;  
20.     };  
21. };  
22.   
23. class Dinic  
24. {  
25. private:  
26.     int s,t,c,m,n;  
27.     vector<Edge>edges;  
28.     vector<int>G[maxn];  
29.     bool vis[maxn];  
30.     int dist[maxn];  
31.     int cur[maxn];  
32. public:  
33.     void AddEdge(int from,int to,int cap)  
34.     {  
35.         Edge e(from,to,cap,0);  
36.         edges.push_back(e);  
37.         e.from=to;  
38.         e.to=from;  
39.         e.cap=0;  
40.         edges.push_back(e);  
41.         c=edges.size();  
42.         G[from].push_back(c-2);  
43.         G[to].push_back(c-1);  
44.     }  
45.     bool BFS()  
46.     {  
47.         queue<int>Q;  
48.         memset(vis,0,sizeof(vis));  
49.         Q.push(s);  
50.         dist[s]=0;  
51.         vis[s]=1;  
52.         while(!Q.empty())  
53.         {  
54.             int x=Q.front();  
55.             Q.pop();  
56.             for(int i=0; i<G[x].size(); i++)  
57.             {  
58.                 Edge& e=edges[G[x][i]];  
59.                 if(!vis[e.to]&&e.cap>e.flow)  
60.                 {  
61.                     vis[e.to]=1;  
62.                     dist[e.to]=dist[x]+1;  
63.                     Q.push(e.to);  
64.                 }  
65.             }  
66.         }  
67.         return vis[t];  
68.     }  
69.     int DFS(int x,int a)  
70.     {  
71.         if(x==t||a==0)return a;  
72.         int flow=0,f;  
73.         for(int& i=cur[x]; i<G[x].size(); i++)  
74.         {  
75.             Edge& e=edges[G[x][i]];  
76.             if(dist[x]+1==dist[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)  
77.             {  
78.                 e.flow+=f;  
79.                 edges[G[x][i]^1].flow-=f;  
80.                 flow+=f;  
81.                 a-=f;  
82.                 if(a==0)break;  
83.             }  
84.         }  
85.         return flow;  
86.     }  
87.     int Maxflow(int s,int t)  
88.     {  
89.         this->s=s;  
90.         this->t=t;  
91.         int flow=0;  
92.         while(BFS())  
93.         {  
94.             memset(cur,0,sizeof(cur));  
95.             flow+=DFS(s,INF);  
96.         }  
97.         return flow;  
98.     }  
99.     void init()  
100.     {  
101.         edges.clear();  
102.         for(int i=0; i<maxn; i++)  
103.         {  
104.             G[i].clear();  
105.             dist[i]=0;  
106.         }  
107.     }  
108. } Do;  
109. int main()  
110. {  
111.     int n,m,k,hp,t;  
112.     cin>>t;  
113.     while(t--)  
114.     {  
115.         cin>>n>>m;  
116.         Do.init();  
117.         for(int i=1; i<=n; i++)  
118.         {  
119.             Do.AddEdge(0,i,1);  
120.             cin>>k;  
121.             int tar;  
122.             for(int j=1; j<=k; j++)  
123.             {  
124.                 cin>>tar;  
125.                 Do.AddEdge(i,n+tar,1);  
126.             }  
127.         }  
128.         for(int i=1; i<=m; i++)  
129.         {  
130.             cin>>hp;  
131.             Do.AddEdge(n+i,n+m+1,hp);  
132.         }  
133.         cout<<Do.Maxflow(0,n+m+1)<<endl;  
134.   
135.     }  
136.     return 0;  
137. }  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define INF 0x7fffffff
using namespace std;
const int maxn=1010;
class Edge
{
public :
    int from,to,cap,flow;
    Edge(int fr,int t,int c,int fl)
    {
        from=fr;
        to=t;
        cap=c;
        flow=fl;
    };
};

class Dinic
{
private:
    int s,t,c,m,n;
    vector<Edge>edges;
    vector<int>G[maxn];
    bool vis[maxn];
    int dist[maxn];
    int cur[maxn];
public:
    void AddEdge(int from,int to,int cap)
    {
        Edge e(from,to,cap,0);
        edges.push_back(e);
        e.from=to;
        e.to=from;
        e.cap=0;
        edges.push_back(e);
        c=edges.size();
        G[from].push_back(c-2);
        G[to].push_back(c-1);
    }
    bool BFS()
    {
        queue<int>Q;
        memset(vis,0,sizeof(vis));
        Q.push(s);
        dist[s]=0;
        vis[s]=1;
        while(!Q.empty())
        {
            int x=Q.front();
            Q.pop();
            for(int i=0; i<G[x].size(); i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to]&&e.cap>e.flow)
                {
                    vis[e.to]=1;
                    dist[e.to]=dist[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a)
    {
        if(x==t||a==0)return a;
        int flow=0,f;
        for(int& i=cur[x]; i<G[x].size(); i++)
        {
            Edge& e=edges[G[x][i]];
            if(dist[x]+1==dist[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }
    int Maxflow(int s,int t)
    {
        this->s=s;
        this->t=t;
        int flow=0;
        while(BFS())
        {
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,INF);
        }
        return flow;
    }
    void init()
    {
        edges.clear();
        for(int i=0; i<maxn; i++)
        {
            G[i].clear();
            dist[i]=0;
        }
    }
} Do;
int main()
{
    int n,m,k,hp,t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        Do.init();
        for(int i=1; i<=n; i++)
        {
            Do.AddEdge(0,i,1);
            cin>>k;
            int tar;
            for(int j=1; j<=k; j++)
            {
                cin>>tar;
                Do.AddEdge(i,n+tar,1);
            }
        }
        for(int i=1; i<=m; i++)
        {
            cin>>hp;
            Do.AddEdge(n+i,n+m+1,hp);
        }
        cout<<Do.Maxflow(0,n+m+1)<<endl;

    }
    return 0;
}

1008         KiKi的难题

这题是一个简单的三维的dp。

Intdp[110][110][110];

dp[i][j][k] 表示第i个岛屿到第j个岛屿没有挖且使用魔法棒剩余次数为k 所能获得大最大价值

[cpp]
view plaincopyprint?

1. for(int i=n-1; i>=1; i--)//枚举剩余岛屿的个数
     
2. for(int j=1;j+i-1<=n; j++)//枚举最左边的岛屿位置
     
3. for(int k=0; k<=m; k++)//枚举魔法棒可使用的次数
     
4. {  
5.         int add=j+i-1;  
6.         if(j!=1)  
7.            {  
8.                     dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k]+p[j-1]);  
9.                     dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k+1]+(m-k)*p[j-1]);  
10.            }  
11.            if(add!=n)  
12.            {  
13.                     dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k]+p[add+1]);  
14.                     dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k+1]+(m-k)*p[add+1]);  
15.            }  
16. }  

for(int i=n-1; i>=1; i--)//枚举剩余岛屿的个数
for(int j=1;j+i-1<=n; j++)//枚举最左边的岛屿位置
for(int k=0; k<=m; k++)//枚举魔法棒可使用的次数
{
        int add=j+i-1;
        if(j!=1)
           {
                    dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k]+p[j-1]);
                    dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k+1]+(m-k)*p[j-1]);
           }
           if(add!=n)
           {
                    dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k]+p[add+1]);
                    dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k+1]+(m-k)*p[add+1]);
           }
}

最后输出最大值就可以了。

标准程序：

[cpp]
view plaincopyprint?

1. #include<iostream>
     
2. #include<cstdio>
     
3. #include<cstring>
     
4. #include<string>
     
5. #include<vector>
     
6. #include<cstdlib>
     
7. #include<stack>
     
8. #include<queue>
     
9. #include<map>
     
10. #include<algorithm>
      
11. using namespace std;  
12. int dp[110][110][110];  
13. int main(){  
14.     int t;cin>>t;  
15.     int n,m,p[110];  
16.     while(t--){  
17.         cin>>n>>m;  
18.         for(int i=1;i<=n;i++) cin>>p[i];  
19.         memset(dp,0,sizeof(dp));  
20.         for(int i=n-1; i>=1; i--)  
21.         {  
22.             for(int j=1; j+i-1<=n; j++)  
23.                 for(int k=0; k<=m; k++)  
24.                 {  
25.                     int add=j+i-1;  
26.                     if(j!=1)  
27.                     {  
28.                         dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k]+p[j-1]);  
29.                         dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k+1]+(m-k)*p[j-1]);  
30.                     }  
31.                     if(add!=n)  
32.                     {  
33.                         dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k]+p[add+1]);  
34.                         dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k+1]+(m-k)*p[add+1]);  
35.                     }  
36.                 }  
37.         }  
38.         int mmax=0;  
39.         if(m==0) cout<<dp[1][1][0]+p[1]<<endl;  
40.         else{  
41.              for(int i=1;i<=n;i++) mmax=max(mmax,dp[i][i][1]+p[i]*m);  
42.              cout<<mmax<<endl;  
43.         }  
44.     }  
45.     return 0;  
46. }  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
int dp[110][110][110];
int main(){
    int t;cin>>t;
    int n,m,p[110];
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>p[i];
        memset(dp,0,sizeof(dp));
        for(int i=n-1; i>=1; i--)
        {
            for(int j=1; j+i-1<=n; j++)
                for(int k=0; k<=m; k++)
                {
                    int add=j+i-1;
                    if(j!=1)
                    {
                        dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k]+p[j-1]);
                        dp[j][add][k]=max(dp[j][add][k],dp[j-1][add][k+1]+(m-k)*p[j-1]);
                    }
                    if(add!=n)
                    {
                        dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k]+p[add+1]);
                        dp[j][add][k]=max(dp[j][add][k],dp[j][add+1][k+1]+(m-k)*p[add+1]);
                    }
                }
        }
        int mmax=0;
        if(m==0) cout<<dp[1][1][0]+p[1]<<endl;
        else{
             for(int i=1;i<=n;i++) mmax=max(mmax,dp[i][i][1]+p[i]*m);
             cout<<mmax<<endl;
        }
    }
    return 0;
}

以上即是本次比赛的全部解题报告以及部分标准程序代码，感谢大家对我校比赛的支持！