一道区间dp和一道字符串

时间  2020-09-14 标签 一道 区间 dp 一道 字符串

 

牛X网测试rating系统，叶神开的bnu的重现赛，送8个T恤，就作了两个题参与下抽奖，打了三场了，不出意料的都没抽中我 =-=ios

 第一道：c++

小Q同窗为了准备今年的ICPC Regional，计划在m天以内刷掉n道题，每道题有一个难度值，其中第i道题的难度值为a[i]。app

然而处于半颓废状态中的小Q同窗不但愿在同一天中作难度差距悬殊的题目，定义第i天中刷的题的难度的最大值减最小值为d[i]（若是第i天没有刷题，则d[i]=0），那么整个计划的难度为\sum_{i=1}^{m}{d^2[i]}。函数

小Q同窗能够按照任意的顺序刷题，而且一天中能够刷任意多道题，可是每道题只须要作一次，如今小Q同窗想知道完成这个计划的总难度的最小值是多少。测试

 

Input

第一行是一个正整数T(\leq 10)，表示测试数据的组数，优化

对于每组测试数据，google

第一行是两个整数n(1\leq n \leq 500)和m(1\leq m \leq 500)，表示题数和天数，spa

第二行是n个整数a[i](0\leq a[i]\leq 1000000)，表示每道题的难度值。设计

 

Output

对于每组测试数据，输出一个整数，表示整个计划的最小难度。3d

 

Sample Input

2
3 3
1 2 3
3 2
1 2 3

Sample Output

0
1

Hint

对于第一组样例，最优方案是一天刷一题。

对于第二组样例，一个最优方案是第一天刷难度值为1和2的题，次日刷难度值为3的题。

 

区间dp了，天数就是区间个数，天天的难度就是一个区间的最大最小差的平方，

求差值平方最小，因此难度相近的一块儿作，排好序，只要找到已排序的全部题如何分割为m份便可。

这里时限5s很宽，直接三重暴力便可：

dp[i][j]表示前i天作j题的最小难度

新加入第j道题的时候，再加一重循环，遍历前状态中每道题，组成新的区间

dp[i][j] = min(dp[i][j],dp[i-1][k-1]+abs(a[j]-a[k])*abs(a[j]-a[k])); j和k为新的区间

参考数据 2 4 6 8  2天完成 能够 2 4一天 6 8 一天 结果8

　　　　　　　　　　　　也能够 2 4 6 一天 8一天 结果16 

显然 新加入的8找6组成区间值更小一些，再加上 dp[1][2]也就是1天作 2 4道题的状态 是最优值

 

固然能够用斜率DP优化到二维，

能够说是斜率优化dp的水题，找个好的模板把那几个函数改下也能够

注意初始化那里通常int的已经不行了，普通的4个3f要改为long long的8个3f，还有就是30行必须提早初始化，在转移方程里比较dp[i-1][j]会出现无限大比较无限大的错误

 1 #include <bits/stdc++.h>
 2 typedef long long ll;
 3 
 4 const ll INF = 0x3f3f3f3f3f3f3f3f;//这里必需要设置超过int的，否则WA，后台数据硬
 5 const int N = 500+10; 6 using namespace std; 7 int n,m,sum,res,flag; 8 long long a[N],dp[N][N]; 9 void init() 10 { 11 for(int i=1;i<=n;i++) 12 dp[0][i]=INF;//这种状况是无限大的 13 dp[0][0] = 0; 14 } 15 int main() 16 { 17 // freopen("in.txt","r",stdin); 18 int i,j,k,cas,T,t,x,y,z; 19 scanf("%d",&T); 20 cas=0; 21 while(T--) 22  { 23 scanf("%d%d",&n,&m); 24  init(); 25 for(i=1;i<=n;i++)scanf("%lld",&a[i]); 26 sort(a+1,a+1+n); 27 for(i=1;i<=m;i++) 28 for(j=1;j<=n;j++) 29  { 30 dp[i][j] = dp[i-1][j]; 31 for(k=1;k<=j;k++) { 32 33 // printf("dp[%d][%d]:%d\n",i,j,dp[i][j]); 34 // cout<<"dp[i-1][k-1]+abs(a[j]-a[k])*abs(a[j]-a[k]): "<<dp[i-1][k-1]+abs(a[j]-a[k])*abs(a[j]-a[k])<<endl; 35 dp[i][j] = min(dp[i][j],dp[i-1][k-1]+abs(a[j]-a[k])*abs(a[j]-a[k])); 36 // printf("前%d天作%d道题的最小难度是%d\n",i,j,dp[i][j]); 37  } 38  } 39 printf("%lld\n",dp[m][n]); 40  } 41 return 0; 42 }

 

 

又到了一年一度的北京师范大学程序设计竞赛！本次比赛的负责人萌萌哒whalyzh同窗要给你们发比赛帐号。因为参赛队伍众多，面对长长的参赛名单，whalyzh同窗表示压力山大。如今whalyzh同窗实在忙不过来，就扔了一份参赛队伍的帐号列表给你。为了肯定给校内队伍颁发的各种奖项的名额，他须要知道一共有多少支校内队伍参加了比赛。

 

Input

第一行是一个正整数T(\leq1000)，表示测试数据的组数，

对于每组测试数据，

第一行是一个整数n(0 \leq n \leq100)，表示队伍数量，

接下来n行，每行是一个格式为"学校英文名缩写16-队伍编号"的字符串，表示队伍帐号，保证学校英文名缩写只包含小写字母，编号是正整数且不含前导零，同一学校不一样队伍的编号必定不一样，来自不一样学校的队伍的编号可能相同。

更多信息请参考样例。

 

Output

对于每组测试数据，输出一行，包含一个整数，表示参赛列表中本校（即学校英文名缩写是"bnu"的队伍）队伍的数量。

 

Sample Input

2
10
bac16-1
bit16-1
bitss16-1
bjfu16-1
bjtu16-1
bnu16-1
buaa16-1
cuc16-1
cugb16-1
google16-1
5
bnu16-1
bnu16-3
bnu16-5
bnu16-2
bnu16-4

Sample Output

1
5

Hint

对于第一组样例，只有"bnu16-1"是校内队伍。

对于第二组样例，全部队伍都是校内队伍。

 

直接找到bnu的队伍set去重便可，map标记也能够，q神说有小坑，可是不知道在哪里=-=

#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>

using namespace std;
set<string> co;
int main()
{
//    freopen("in.txt","r",stdin);
    int T;
    cin>>T;
    while(T--) {
        co.clear();
        int n;
        cin>>n;
        for(int i = 0; i < n; i++) {
        string s;
        cin>>s;
        if(s.substr(0,6)=="bnu16-") {
            co.insert(s);
            }
        }
        cout<<co.size()<<endl;
    }
    return 0;
}
联系我们 沪ICP备2021010478号-7