当某八个同校猜的队列在硬币体系中出现时,划分为多少字串

4820: [Sdoi2017]硬币游戏

Time Limit: 10 Sec  Memory
Limit: 128 MB

壹 、UVa 11584 Partitioning by
Palindromes(字符串区间dp)

1062 ModricWang的撒币游戏

Description

周一同窗们卓殊无聊,有人建议,大家扔硬币玩吧,何人扔的硬币正面次数多何人胜利。大家纷繁认为那几个娱乐至极符

合同学们的风味,但只是扔硬币实在是太枯燥了。同学们以为要拉长趣味性,所以要找贰个同室扔很多很频仍硬币

,其余同学记录下正面与反面面情形。用H代表尊重朝上,用T代表反面朝上,扔很频仍硬币后,会得到2个硬币连串。比

如HTT表示第2回正面朝上,后四回反面朝上。但扔到如曾几何时候停止呢?大家提议,选出n个同学,种种同学猜二个

长度为m的行列,当某1个同桌猜的行列在硬币系列中出现时,就不再扔硬币了,并且那些同桌胜利,为了确定保证只

有多少个同桌胜利,同学们猜的n个体系两两不一致。一点也不慢,n个同学猜好连串,然后进入了紧张而又刺激的扔硬币环节

。你想知道,假诺硬币正面与反面面朝上的概率一样,每种同学胜利的概率是多少。

  题意:给出一个字符串,划分为多少字串,保险每种字串都是回文串,同时划分数目最小。

思路

此题为二〇一七年ACM-ICPC澳大累西腓区域赛伊Lisa白港赛区的A题,现场9五个队中有叁16个队做出此题。在此间当做满分以外的题,是为了让我们看一下外边一些题的品格,不要被2个人教授的出题风格所局限。

此题首先供给知道有个别高中数学可能率论的知识。扔起N个硬币,固然每种硬币下跌时,正面与反面面朝上的票房价值都是规定的,那么这几个硬币中正面朝上的数据是呈二项分布的。

考虑选拔DP,\(prob[i][j]\)
表示扔了第i次后,有j个硬币正面朝上的可能率。首先根据题设,\(prob[0][0]=1\),每一回依照\(i\)这一行来生产\(i+1\)这一行,扔硬币的进度会让\(prob[i][j]\) 以二项分布分散到\(prob[i+1][p]和prob[i+1][p+k]\)
这\(k+1\)
项里。j、p和n的涉嫌如下:\(p \leq j \leq
p+k \leq n\)
,意义为:j表示如今有稍许个硬币向上,p表示下一步最少有微微个硬币向上,(p+k)表示下一步最多有些许个硬币向上。所谓的最优策略正是,让p尽量的大,也便是扔硬币的时候尽量选朝下的扔。最后答案正是
\(\Sigma_{i=1}^{n}
i*prob[m][i]\)。

切实进展操作时能够有一对优化策略,例如

  • 动用滚动数组来节省空间
  • 忽视可能率小于\(1e-3\) 的项

但是本人做的时候从不采取这个策略,因为

  • 依照测算,内部存款和储蓄器空间是十足的
  • 虽然\(O(Tnmk)\)
    在此题中完毕了\(1e9\)的数量级,不过总计进度中的宗旨语句是\(a+=b*c\)
    的样式,那样的话语在X86架构下就是一条FMA指令的事,不必顾虑常数的标题。
    reference: 乘积累加运算 –
    维基百科

    and FMA指令集 –
    维基百科

时间复杂度:\(O(Tnmk)\),空间复杂度\(O(nm)\)

Input

先是行七个整数n,m。

收下里n行,每行多少个长度为m的字符串,表示第i个同学猜的队列。

1<=n,m<=300

  思路:dp[i]表示以第i位结尾时最小的剪切数目(初步均为0)

代码:

#include <iostream>
#include <iomanip>
#include <cstring>

using std::ios_base;
using std::cin;
using std::cout;
using std::min;
using std::fixed;
using std::setprecision;

const int MaxNum = 100 + 7;

double prob[MaxNum][MaxNum];

double binomial_distribution[MaxNum][MaxNum];

//计算二项分布的概率值
void get_binomial_distribution() {
    double prob_sum = 1;
    for (int i = 1; i < MaxNum; i++) {
        double C = 1;
        prob_sum *= 2;
        binomial_distribution[i][0] = C/prob_sum;
        for (int j = 1; j <= i; j++) {
            C = C*(i - j + 1)/j;
            binomial_distribution[i][j] = C/prob_sum;
        }
    }
}

int main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#else
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    get_binomial_distribution();

    int T;
    while (cin >> T) {
        while (T--) {
            int n, m, k;
            cin >> n >> m >> k;
            memset(prob, 0, sizeof(prob));
            prob[0][0] = 1;
            for (int step = 1; step <= m; step++) {
                for (int i = 0; i <= n; i++) {
                    int begin_pos = min(i, n - k);  //这就是思路里写的p
                    for (int j = 0; j <= k; j++) {
                        prob[step][begin_pos + j] += prob[step - 1][i]*binomial_distribution[k][j]; //DP过程
                    }
                }
            }
            double ans = 0;
            for (int i = 1; i <= n; i++) {
                ans += i*prob[m][i];
            }
            cout << fixed << setprecision(3) << ans << "\n";
        }
    }
}

Output

输出n行,第i行代表第i个同学胜利的可能率。

输出与行业内部输出的相对误差不超过10^-6即视为正确。

    状态转移方程1:(起首均为0)当[j:i]是回文串(0≤j≤i,0≤i<n):dp[i]=1(j==0);dp[i]=(dp[i]==0?dp[j-1]+1:min(dp[i],dp[j-1]+1))

Sample Input

3 3
THT
TTH
HTT

    状态转移方程2:(初阶:dp[i]=i+1)当[j:i]是回文串(0≤j≤i,0≤i<n):dp[i]=1(j==0);dp[i]=min(dp[i],dp[j-1]+1))

Sample Output

0.3333333333
0.2500000000
0.4166666667

 

题解:

生无可恋.jpg

在自身做过的题里继小凸玩密室又一神题啊……小编可能学了假的票房价值DP

上来大家得以窥见那本是一道字符集为2的AC自动机的DP,飞快码好读入和拍卖fail指针。

下一场我们后续套路,发现那些赢球概率在Trie图上相互制约无法递推,所以我们要用高斯消元。

……高斯消元?

假定我们对此每一种AC自动机的节点都这么做的话,仅时间复杂度就改为了O(3006),间接螺旋上天了。

那正是说大家只可以不考虑每种节点,而是考虑每个串了。

设p[i]为第i个同学获胜的概率,也正是说第一个地位卓殊到第i个串的票房价值。

第1大家能够列出首个方程:Σp[i]=1.0

那正是说大家考虑,在3个不是单词节点的节点,假使已经通过的字符状态为S,

比方大家向后面添加m个字符,那么泾渭鲜明,由于大家是一心自由添加的,所以匹配到各种串i的票房价值都以一模一样的,大家设为H。

简单看出,假使大家相配到i,那么这种增进格局得以分包全体匹配到i的意况。

然而那里H不自然等于p[i]:大家透过每一个非单词节点的可能率也不必然一样;

再正是同时,由于大家事先曾经十二分了状态为S的一些字符,大家只怕在拉长不到m个字符时就同盟到了有个别串j(j能够等于i)

只要在有些节点加上字符串i的前k个字符后就早已抵达了字符串j的终止节点,那么j的后k个字符必然等于i的前k个字符.

在卓越上j后,(纵然一而再协作是私行的,不过大家要减去那种私行状态,所以大家还要总括这种情景产生的可能率.)

咱俩还要持续生成字符使得接下去m-k的字符等于串i的后m-k个字符,约等于说,p[i]相应在H的根基上减去p[j]*(1/2)m-k

此地的“前k个字符重叠”,我们得以行使KMP的失配指针来拍卖。

(其实那里的处理办法有诸多,除了kmp,hash也足以,只要能找出两串的重叠部分即可)

那便是说最后,大家得以列出方程:p[i]=H-Σp[j]*(1/2)m-k,移项得p[i]+Σp[j]*(1/2)m-k-H=0

再加上一方始的方程Σp[i]=1.0,大家就能够对n+1个变量列出n+3个方程来解方程了!

代码见下:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N=310;
 7 int n,l,cnt,fail[N<<1];
 8 char s[N][N],str[N<<1];
 9 double f[N][N];
10 inline void kmp()
11 {
12     register int i,j,len;
13     for(i=2,j=0,len=(l<<1);i<=len;++i)
14     {
15         while(j&&str[j+1]!=str[i])j=fail[j];
16         j=(str[j+1]==str[i])?j+1:j,fail[i]=j;
17     }
18 }
19 void Swap(int a,int b)
20     {for(register int i=1;i<=cnt+1;++i)swap(f[a][i],f[b][i]);}
21 void Execution(int a,int b,double t)
22     {for(register int i=1;i<=cnt+1;++i)f[a][i]+=f[b][i]*t;}
23 inline void gauss()
24 {
25     register int i,j,k;
26     for(i=1;i<=cnt;++i)
27     {
28         for(j=i+1;j<=cnt;++j)if(fabs(f[i][i])<fabs(f[j][i]))Swap(i,j);
29         for(j=1;j<=cnt;++j)if(j!=i)Execution(j,i,-f[j][i]/f[i][i]);
30     }
31     for(i=1;i<=cnt;++i)f[i][cnt+1]/=f[i][i];
32 }
33 int main()
34 {
35     scanf("%d%d",&n,&l);register int i,j,k;
36     for(i=1;i<=n;++i)scanf("%s",s[i]+1);
37     for(i=1;i<=n;++i)
38         for(j=1;j<=n;++j)
39         {
40             for(k=1;k<=l;++k)str[k]=s[i][k],str[l+k]=s[j][k];
41             for(kmp(),k=fail[l<<1];k;k=fail[k])
42                 if(k<l)f[i][j]+=pow(0.5,l-k);
43         }
44     for(i=1;i<=n;++i)f[i][i]+=1.0,f[i][n+1]-=1.0;//n+1代表未知变量H
45     for(i=1,f[n+1][n+2]=1.0;i<=n;++i)f[n+1][i]=1.0;
46     cnt=n+1;gauss();
47     for(i=1;i<=n;++i)printf("%.10lf\n",f[i][cnt+1]);
48 }

 

    状态转移方程3:(初阶:dp[i]=i+1(1≤i≤n);其他:dp[i]=0)当[j:i]是回文串(1≤j≤i,1≤i≤n):dp[i]=min(dp[i],dp[j-1]+1))

图片 1图片 2

 1 #include<iostream>
 2 #include<memory.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<cstdio>
 6 using namespace std;
 7 const int maxn = 1005;
 8 char s[maxn];
 9 int dp[maxn];
10 int n;
11 bool Judge(int st, int ed)
12 {
13     for (; st <= ed; st++, ed--)
14     {
15         if (s[st] != s[ed]) return false;
16     }
17     return true;
18 }
19 int main()
20 {
21     cin >> n;
22     while (n--)
23     {
24         scanf("%s", s);
25         memset(dp, 0, sizeof(dp));
26         int sz = strlen(s);
27         for (int i = 0; i < sz; i++)
28         {
29             for (int j = 0; j <= i; j++)
30             {
31                 if (Judge(j, i))
32                 {
33                     if (j == 0) dp[i] = 1;
34                     else dp[i] = dp[i] == 0 ? dp[j - 1] + 1 : min(dp[i], dp[j - 1] + 1);
35                 }
36             }
37         }
38         cout << dp[sz - 1] << endl;
39     }
40     return 0;
41 }

View Code

2、UVA 10534 Wavio Sequence(dp +
LIS)

  题意:给出二个字符串,求满意如此条件的子系列的最大尺寸:长度为奇数(借使为2*k+1),同时前k+二个严谨递增,后k+二个严格递减。

  思路:分别从左往右和从右往左分别算出以第i位结尾的最长递增子体系的长度L一 、L2,然后得出以第i位为大旨的知足条件的子系列的尺寸:min(L1,L2)*2-1(若是L一 、L2包罗该位),然后对每一位分别重复上述操作,得出最大尺寸。

图片 3图片 4

 1 #include<iostream>
 2 #include<vector>
 3 #include<memory.h>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 10005;
 7 int maxl[maxn];
 8 int maxr[maxn];
 9 int p[maxn];
10 void exchange(int x, int pos, vector<int>&v, char c)
11 {
12     vector<int>::iterator it;
13     it = lower_bound(v.begin(), v.end(), x);
14     int p = it - v.begin();
15     v[p] = x;
16     if (c == 'l')maxl[pos] = p;
17     else maxr[pos] = p;
18 }
19 int main()
20 {
21     int n;
22     while (cin >> n)
23     {
24         vector<int>minlen;
25         for (int i = 0; i < n; i++) cin >> p[i];
26         minlen.push_back(p[0]);
27         maxl[0] = 0;
28         for (int i = 1; i < n; i++)
29         {
30             if (p[i] > minlen.back())
31             {
32                 maxl[i] = minlen.size();
33                 minlen.push_back(p[i]);
34             }
35             else
36             {
37                 exchange(p[i], i, minlen, 'l');
38             }
39         }
40         minlen.clear();
41         minlen.push_back(p[n - 1]);
42         maxr[n - 1] = 0;
43         for (int i = n - 2; i >= 0; i--)
44         {
45             if (p[i] > minlen.back())
46             {
47                 maxr[i] = minlen.size();
48                 minlen.push_back(p[i]);
49             }
50             else
51             {
52                 exchange(p[i], i, minlen, 'r');
53             }
54         }
55         int len = 0;
56         for (int i = 0; i < n; i++)
57         {
58             int tmp = min(maxl[i], maxr[i]) * 2 + 1;
59             if (tmp > len) len = tmp;
60         }
61         cout << len << endl;
62     }
63     return 0;
64 }

View Code

3、uva 11404 – Palindromic
Subsequence(dp)

  题意:给出3个字符串,求其最长回文子串,并出口该字串。若是有三个,输出字典序最小的十三分。

  思路:假使只求长度:dp[i][j]=dp[i+1][j-1]+2(s[i]==s[j]);dp[i][j]=max(dp[i+1][j],dp[i][j-1])(s[i]!=s[j])

    在此基础上得以用string来保存一时回文子串。

图片 5图片 6

 1 #include<iostream>
 2 #include<string>
 3 #include<memory.h>
 4 using namespace std;
 5 const int maxn = 1005;
 6 struct node
 7 {
 8     int len;
 9     string str;
10 }dp[maxn][maxn];
11 
12 int main()
13 {
14     string s;
15     while (cin >> s)
16     {
17         int len = s.length();
18         memset(dp, 0, sizeof(dp));
19         for (int i = 0; i < len; i++)
20         {
21             dp[i][i].len = 1;
22             dp[i][i].str = s[i];
23         }
24         for (int i = len - 1; i >= 0; i--)
25         {
26             for (int j = i; j < len; j++)
27             {
28 
29                 if (s[i] == s[j])
30                 {
31                     if (i == j)
32                     {
33                         dp[i][j].len = 1;
34                         dp[i][j].str = s[i];
35                     }
36                     else
37                     {
38                         dp[i][j].len = dp[i + 1][j - 1].len + 2;
39                         dp[i][j].str = s[i] + dp[i + 1][j - 1].str + s[j];
40                     }
41                 }
42                 else
43                 {
44                     if (dp[i + 1][j].len > dp[i][j - 1].len)
45                     {
46                         dp[i][j].len = dp[i + 1][j].len;
47                         dp[i][j].str = dp[i + 1][j].str;
48                     }
49                     else if (dp[i + 1][j].len < dp[i][j - 1].len)
50                     {
51                         dp[i][j].len = dp[i][j - 1].len;
52                         dp[i][j].str = dp[i][j - 1].str;
53                     }
54                     else
55                     {
56                         dp[i][j].len = dp[i][j - 1].len;
57                         if (dp[i][j - 1].str < dp[i + 1][j].str) dp[i][j].str = dp[i][j - 1].str;
58                         else dp[i][j].str = dp[i + 1][j].str;
59                     }
60                 }
61             }
62         }
63         cout << dp[0][len - 1].str << endl;
64     }
65     return 0;
66 }

View Code

④ 、UVA 11795 – Mega Man’s
Mission(状态压缩dp)

  题意:Locke人手里有一把武器,能够杀死部分特定敌人(可以杀死的记为1,无法杀死的记为0),同时,他杀死敌人后,能够利用被杀死的敌人的火器,其武器同样也不得不杀死一定的大敌。求能杀死全部仇敌的方案数。

  思路:对于n个敌人,共有2^n-1种景况(用二个int即可表示),能够先求出各样状态下能够杀死的仇敌atk[i](即该意况i下杀死的大敌的兵器被拿走后能够杀死的仇敌),之后,对于i那种意况,假诺该情形下能够杀死仇人j,如若i^(1<<j)那种情状(不可能杀死j)下能够杀死j(atk[i^(1<<j)]&1<<j),则dp[i]+=dp[i^(1<<j)]。

图片 7图片 8

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<memory.h>
 4 using namespace std;
 5 typedef long long ll;
 6 char s[20];
 7 const int maxn = (1 << 16) + 10;
 8 int N;
 9 int w[maxn];//存储洛克人[0]和敌人[1:]的武器
10 int atk[maxn];//用来保存每个状态可以杀死的机器人
11 ll dp[maxn];// 2 的 16 次方会爆 int。 // 用来统计每种状态的顺序方案种数
12 int Exchange()
13 {
14     int ans = 0;
15     int sz = strlen(s);
16     for (int i = 0; i < sz; i++)
17     {
18         if (s[i] == '1') ans = ans | (1 << i);//第i+1位如果能被杀掉,则第i+1位为1
19     }
20     return ans;
21 }
22 int main()
23 {
24     int T;
25     cin >> T;
26     int Case = 1;
27     while (T--)
28     {
29         cin >> N;
30         for (int i = 0; i <= N; i++)
31         {
32             scanf("%s", s);
33             w[i] = Exchange();
34             //cout << i << ' ' << w[i] << endl;
35         }
36         int total = (1 << N) - 1;//对于N个敌人,一共最多有2^N-1种状态(每个敌人能够杀死或不能杀死)
37         for (int st = 0; st <= total; st++)
38         {//st即为二进制存储的状态
39             atk[st] = w[0];//初始为洛克人所拿的武器能够杀死的人
40             for (int i = 1; i <= N; i++)//对于每个敌人
41             {
42                 int j = i - 1;//i其在所存二进制里的位置
43                 if (st&(1 << j))
44                 {//如果该状态可以杀死 i,那么该状态也可以杀死i所能干掉的
45                     atk[st] = atk[st] | w[i];
46                 }
47             }
48         }
49         memset(dp, 0, sizeof(dp));
50         dp[0] = 1;//一个都不杀死的方案数为1
51         for (int st = 1; st <= total; st++)
52         {
53             for (int i = 0; i < N; i++)
54             {//对于N个敌人
55                 if (st & 1 << i)
56                 {//如果该状态能够杀死第i+1个敌人(敌人从1开始编号,但是在二进制存储的杀死状态中存储的位置为i),那么 st 由不能杀死 i 的状态转移过来, 即st^(1<<i)(异或)
57                     if (atk[st ^ (1 << i)] & 1 << i)//并且st^(1<<i)这种状态能够杀死该敌人
58                     {
59                         dp[st] += dp[st ^ (1 << i)];
60                     }
61                 }
62             }
63         }
64         printf("Case %d: %lld\n", Case++, dp[total]);
65     }
66     return 0;
67 }

View Code

5、UVA 10564 Paths through the
Hourglass(dp)

  题意:有二个漏斗形的图,从某一行只可以向左下或右下走,走过的路径上的罗列之和要等于S。求路径数,若存在,则输出从第壹行最右侧伊始,同时所走方向形成的字典序最小的字符串。(由‘L’、‘LX570’组成)。

  思路:从下往上dp,dp[i][j][k]
代表从(i,
j)点往下走到终极一层和为k的方案数,那么,鲜明能够赢得气象转移:

  dp[i][j][k] = dp[i +
1][left][k – val] + dp[i + 1][right][k – val], val = (i,
j)格上的数字,left是往坐下走的坐标,right往右下走的坐标

图片 9图片 10

  1 #include<iostream>
  2 #include<memory.h>
  3 #include<cstdio>
  4 using namespace std;
  5 typedef long long ll;
  6 int N, S;
  7 ll dp[50][50][510];
  8 int m[50][50];
  9 void Input()
 10 {
 11     for (int i = 1; i <= N; i++)
 12     {
 13         for (int j = 1; j <= N - i+1; j++)
 14         {
 15             scanf("%d", &m[i][j]);
 16         }
 17     }
 18     for (int i = N+1; i <= 2 * N - 1; i++)
 19     {
 20         for (int j = 1; j <= i - N + 1; j++)
 21         {
 22             scanf("%d", &m[i][j]);
 23         }
 24     }
 25 }
 26 void Print()
 27 {
 28     int pos;
 29     for (int i = 1; i <= N; i++)
 30     {
 31         if (dp[1][i][S])
 32         {
 33             cout <<i-1<< ' ';
 34             pos = i;
 35             break;
 36         }
 37     }
 38     int sum = S;
 39     for (int i = 2; i <= N; i++)
 40     {
 41             if (dp[i][pos - 1][sum - m[i - 1][pos]])
 42             {
 43                 cout << 'L';
 44                 sum -= m[i - 1][pos];
 45                 pos--;
 46             }
 47             else
 48             {
 49                 cout << 'R';
 50                 sum -= m[i - 1][pos];
 51             }
 52     }
 53     for (int j = N+1; j <= 2 * N - 1; j++)
 54     {
 55         if (dp[j][pos][sum - m[j - 1][pos]])
 56         {
 57             cout << 'L';
 58             sum -= m[j - 1][pos];
 59         }
 60         else
 61         {
 62             cout << 'R';
 63             sum -= m[j - 1][pos];
 64             pos++;
 65         }
 66     }
 67     cout << endl;
 68 }
 69 
 70 int main()
 71 {
 72     while (cin >> N >> S, N != 0 || S != 0)
 73     {
 74         Input();
 75         memset(dp, 0, sizeof(dp));
 76         for (int i = 1; i <= N; i++) dp[2 * N - 1][i][m[2 * N - 1][i]] = 1;
 77         for (int i = 2 * N - 2; i >= N; i--)
 78         {
 79             for (int j = 1; j <= i - N + 1; j++)
 80             {
 81                 int v = m[i][j];
 82                 for (int tv = v; tv <= S; tv++)
 83                 {
 84                     dp[i][j][tv] = dp[i + 1][j][tv-v] + dp[i + 1][j + 1][tv-v];
 85                 }
 86             }
 87         }
 88         for (int i = N - 1; i >= 1; i--)
 89         {
 90             for (int j = 1; j <= N - i+1; j++)
 91             {
 92                 int v = m[i][j];
 93                 for (int tv = v; tv <= S; tv++)
 94                 {
 95                     dp[i][j][tv] = dp[i + 1][j][tv-v] + dp[i + 1][j - 1][tv-v];
 96                 }
 97             }
 98         }
 99         ll ans = 0;
100         for (int i = 1; i <= N; i++) ans += dp[1][i][S];
101         if (ans == 0) cout << ans << endl << endl;
102         else
103         {
104             printf("%lld\n", ans);
105             Print();
106         }
107     }
108     return 0;
109 }

View Code

6、UVA 11552 Fewest Flops

  题意:给出多个长度能够整除k的字符串,整除后取得的子串中的字符看可以重新组合。求最终收获的新的字符串中级知识分子足该原则(字串中各类字符都一致)的子串的蝇头数目。例如:“abccd”中,那样的数目有四个:“a”,”b”,”cc”,”d”.

  思路:DP[i][j]意味着前i段,第i段以第j个字符结尾时最小的满意条件的字串数目。

    DP[i][j] = min(DP[i][j],DP[i – 1][l] + cnt –
1)(i-1段以第l个字符结尾时,该字符和第i段率先个字符相同时)

    DP[i][j] = min(DP[i][j],DP[i – 1][l] +
cnt)(i-1段以第l个字符结尾时,该字符和第i段率先个字符分裂时)

 

图片 11图片 12

 1 #include<map>
 2 #include<string>
 3 #include<iostream>
 4 #include<memory.h>
 5 #include<algorithm>
 6 using namespace std;
 7 #define maxn 1020
 8 int dp[maxn][maxn];
 9 int main()
10 {
11     int n;
12     cin >> n;
13     while (n--)
14     {
15         int k;
16         cin >> k;
17         string s;
18         cin >> s;
19         int l = s.length();
20         int tl = l / k;
21         map<char, int>m;
22         int count = 0;
23         memset(dp, 0, sizeof(dp));
24         for (int i = 0; i < k; i++)
25         {
26             if (!m[s[i]])
27             {
28                 m[s[i]] = 1;
29                 count++;
30             }
31         }
32         for (int i = 0; i < k; i++) dp[0][i] = count;
33         for (int j = 1; j<tl; j++)
34         {
35             m.clear();
36             count = 0;
37             for (int i = 0; i < k; i++)
38             {
39                 if (!m[s[i + j*k]])
40                 {
41                     m[s[i + j*k]] = 1;
42                     count++;
43                 }
44             }
45             for (int i = 0; i < k; i++) dp[j][i] = l;
46             for (int i = 0; i < k; i++)
47             {
48                 for (int l = 0; l < k; l++)
49                 {
50                     if (m[s[l + (j - 1)*k]] && (count == 1 || s[l + (j - 1)*k] != s[i + j*k]))
51                     {//如果j-1段中第l个字母在第j段中出现过,并且第j段中字母种类只有一种或者有多种但最后一个字母不是它
52                         dp[j][i] = min(dp[j][i], dp[j - 1][l] + count - 1);
53                     }
54                     else dp[j][i] = min(dp[j][i], dp[j - 1][l] + count);
55                 }
56             }
57         }
58         int mincount = l;
59         for (int i = 0; i < k; i++) mincount = min(mincount, dp[tl - 1][i]);
60         cout << mincount << endl;
61     }
62     return 0;
63 }

View Code

 7、UVa 11825 Hackers’ Crackdown

  题意:有3个分布式互联网,每台电脑都有若干台和它附近,同时持有电脑都有N种服务运作。今后有个黑客,他想要发送病毒,一台总计机只好植入一种病毒,唯有具备电脑都瘫坏才能瘫坏掉一种服务,求其能够干掉的最多的劳动种数。

  思路:2进制状态压缩保存每台电脑的交界状态,并用2进制来保存每个状态下能拿下的总括机。dp[i]意味着i状态下能干掉的最多的劳动数量。dp[i]
= max(dp[i], dp[i^j] + 1)。详细见注释

图片 13图片 14

 1 //状压DP
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxst = (1 << 17);
 6 int ini[20];
 7 int cover[maxst];
 8 int dp[maxst];
 9 int main()
10 {
11     int n;
12     int Case = 1;
13     while (~scanf("%d", &n))
14     {
15         if (n == 0) break;
16         for (int i = 0; i < n; i++)
17         {
18             ini[i] = 0|(1<<i);//包括自身
19             int m;
20             scanf("%d", &m);
21             for (int j = 0; j < m; j++)
22             {
23                 int k;
24                 scanf("%d", &k);
25                 ini[i] |= (1 << k);//加上邻居
26             }
27         }
28         int total = (1 << n) - 1;//总状态数
29         for (int i = 0; i <=total; i++)
30         {
31             cover[i] = 0;
32             for (int j = 0; j < n; j++)
33             {
34                 if (i&(1 << j))//如果该状态能够瘫坏第j台电脑
35                 {
36                     cover[i] |= ini[j];//那么也能瘫坏其邻接的电脑
37                 }
38             }
39         }
40         dp[0] = 0;
41         for (int i = 1; i <= total; i++)
42         {
43             dp[i] = 0;
44             //枚举子集
45             for (int j = i; j > 0; j = (j - 1)&i)
46             {
47                 if (cover[j] == total)//如果子集的状态下能够干掉所有的电脑
48                 {
49                     dp[i] = max(dp[i], dp[i^j] + 1);//那么该状态的能够关闭的服务为max{该状态下能最多关闭的服务数,该状态i和能够干掉所有的电脑的子集的补集所能能关闭的方案数+1(这个1由该子集j提供)}
50                 }
51             }
52         }
53         printf("Case %d: %d\n",Case, dp[total]);
54         Case++;
55     }
56     return 0;
57 }

View Code

 8、UVA-10635 Prince and Princess

  题意:求七个体系的国有最长子连串。

  思路:传闻最长公共子类别算法会超时……由于体系种种数都区别,能够变换为求b的最长递增子连串,只需将a数组按顺序从1从头重复编号,建立映射。

 

图片 15图片 16

 1 #include<iostream>
 2 #include<map>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxl = 300 * 300;
 7 int numa[maxl];
 8 int numb[maxl];
 9 map<int, int>m;
10 void exchange(int x, vector<int>&v)
11 {
12     vector<int>::iterator it;
13     it = lower_bound(v.begin(), v.end(), x);
14     int p = it - v.begin();
15     v[p] = x;
16 }
17 
18 int main()
19 {
20     int t;
21     int Case = 1;
22     scanf("%d", &t);
23     while (t--)
24     {
25         int n, p, q;
26         scanf("%d%d%d", &n, &p, &q);
27         for (int i = 0; i < p+1; i++)
28         {
29             scanf("%d", &numa[i]);
30             m[numa[i]] = i + 1;
31         }
32         for (int i = 0; i < q+1; i++)
33         {
34             scanf("%d", &numb[i]);
35             if (m[numb[i]]) numb[i] = m[numb[i]];
36             else numb[i] = 0;
37         }
38         vector<int>minlen;
39         minlen.push_back(numb[0]);
40         for (int i = 1; i < q+1; i++)
41         {
42             if (numb[i] > minlen.back()) minlen.push_back(numb[i]);
43             else
44             {
45                 exchange(numb[i], minlen);
46             }
47         }
48         printf("Case %d: %d\n",Case, minlen.size());
49         Case++;
50     }
51     return 0;
52 }

View Code

 9、Uva-10891-Game of Sum

  题意:A和B两人,每回能够轮流从一个数组的左端或右端起始拿走多少个数字,直到数组为空,A先手。求最优选拔下A能比B最多高出多少。

  思路:DP,dp[st][ed] = sum[ed]

  • sum[st – 1] – min(0,L[st][ed – 1],R[st +
    1][ed]),L[st][ed] = min(L[st][ed – 1],
    dp[st][ed]);R[st][ed] = min(R[st + 1][ed],
    dp[st][ed]).

图片 17图片 18

 1 #include<cstdio>
 2 #include<string>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 typedef long long ll;
 9 const int INF = 0x3f3f3f3f;
10 const int maxn = 100;
11 int n;
12 //const int maxV=12;
13 int a[maxn + 10];
14 int dp[maxn + 5][maxn + 5];
15 int L[maxn + 5][maxn + 5], R[maxn + 5][maxn + 5];
16 int sum[maxn + 10];
17 int main()
18 {
19     while (~scanf("%d", &n) && n)
20     {
21         for (int i = 1; i <= n; i++)
22             scanf("%d", &a[i]);
23         sum[0] = 0;
24         for (int i = 1; i <= n; i++)
25         {
26             dp[i][i] = a[i];//dp[st][ed]表示[st,ed]区间,先手最多得分。
27             sum[i] = sum[i - 1] + a[i];//L[st,ed]=min{dp[st][k]  } ;(st<=k<=ed)
28             L[i][i] = R[i][i] = dp[i][i];//R[st,ed]=min{dp[k][ed]};(st<=k<=ed)
29         }
30         for (int add = 1; add<n; add++)
31         {
32             for (int st = 1; st + add <= n; st++)
33             {
34                 int ed = st + add;
35                 int m = 0;              //m表示此阶段的后手最少能拿多少
36                 m = min(m, L[st][ed - 1]);//表示从右边拿起
37                 m = min(m, R[st + 1][ed]);//表示从左边拿起
38                 dp[st][ed] = sum[ed] - sum[st - 1] - m;
39                 L[st][ed] = min(L[st][ed - 1], dp[st][ed]);
40                 R[st][ed] = min(R[st + 1][ed], dp[st][ed]);
41             }
42         }
43         printf("%d\n", dp[1][n] - (sum[n] - sum[0] - dp[1][n]));
44     }
45     return 0;
46 }

View Code

 

10、Uva 10859 – Placing Lampposts

  题意:在一张图中,选取结点放置路灯,路灯会照亮连接该结点的门径,问使全体路线都能被照到的纤维路灯数目为多少?同时在颇具最小的方案中,要保险最少被两盏灯照亮的征途最多。

  思路:树形DP。优化:x=M*v1+v2,个中M是比”比v2的最娄底论值和v2的细微理论值之差”还要大的数。v1表示放置的路灯数目尽大概小,v2代表被一盏灯照亮的路尽或许小。v1=x/M,v2=x%M,v3=m-v2.(被两盏灯照亮的路)。每放一盏灯

  • 两千(m)(因为边的最大数据为一千),每扩展1条照亮一回的边 + 1.

  ①节点i处不放街灯,那么i是根可能老爸节点放了街灯。所以dp(i,j)=sum{
dp(v,0) | v取遍i的有所儿子节点
},假诺i不是根节点,那么结果+1,因为i和阿爹总是的那条边只被一盏灯照亮。

  ②节点i处放街灯,dp(i, j) = sum{
dp(v,1) | v取遍i的具有孙子节点 } +M,假设i不是根节点而且j = 0,那么结果

  • 1。

图片 19图片 20

 1 //树形DP
 2 //f(i,j)表示第i盏灯的父亲是否点亮所以j=0|1如果父亲放了,那么自己放或者不放都可以那么f(i,j)=max{∑f(ison,0)∑f(ison,1)},如果父亲没有放置,那么自己必须放那么f(i,0)=∑f(ison,1)但是这个时候要让被灯照亮两次的边尽量多,那么应该让被照亮一次的边尽量的少,那么另m=n×x+yx代表覆盖当前的子树的灯的数量,y代表当前子树中覆盖完成的最少的被照亮一次的边的数量前提是让y的最大值小于n那么这样x就成为了首要重要的权值,y是次要的然后dp方程改一下
 3 
 4 //f(i, 0) = (∑f(ison, 1)) + 1
 5 //加1是因为自己和自己的父亲又有一条边被照亮一次所以加1,
 6 //f(i, 1) = max{ (∑f(ison,0)) + 1,∑f(ison,1) }
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<cstring>
10 #include<cmath>
11 #include<algorithm>
12 #include<string>
13 #include<vector>
14 #include<queue>
15 #include<stack>
16 #define INF 0x3f3f3f3f
17 #define NODENUM 1005
18 #define EDGENUM 1005
19 #define MAXN 1005
20 using namespace std;
21 //优化x=M*v1+v2,其中M是比"比v2的最大理论值和v2的最小理论值之差"还要大的数。v1表示放置的路灯数目尽可能小,v2表示被一盏灯照亮的路尽可能小。v1=x/M,v2=x%M,v3=m-v2.(被两盏灯照亮的路)
22 int root;
23 const int m = 2000;//即理论的M
24 
25 struct EdgeNode
26 {
27     int to, next;
28 } E[2 * EDGENUM];
29 int edgenum, head[NODENUM], N, T, M;
30 bool vis[NODENUM];
31 int ans;
32 int dp[NODENUM][2];//[0]表示不放灯,[1]表示放灯
33 
34 void init()
35 {
36     edgenum = 0;//路条数为0
37     memset(head, -1, sizeof(head));
38     memset(vis, 0, sizeof(vis));
39     ans = 0;
40 }
41 
42 void add(int x, int y)
43 {
44     edgenum++;
45     E[edgenum].next = head[x];
46     head[x] = edgenum;
47     E[edgenum].to = y;
48 }
49 
50 void dfs(int s)
51 {
52     vis[s] = 1;
53     int sum0 = 0, sum1 = 0;
54 
55     for (int p = head[s]; p != -1; p = E[p].next)
56     {
57         int v = E[p].to;
58         if (!vis[v])
59         {
60             dfs(v);
61             sum0 += dp[v][0];
62             sum1 += dp[v][1];
63         }
64     }
65     if (s == root) dp[s][0] = min(sum1 + m, sum0), ans += dp[s][0];
66     else dp[s][1] = min(sum0 + 1, sum1 + m), dp[s][0] = sum1 + m + 1;
67 }
68 //每放一盏灯 + 2000(m)(因为边的最大数量为1000),每增加1条照亮一次的边 + 1.
69 //决策一:节点i处不放街灯,那么i是根或者父亲节点放了街灯。所以dp(i,j)=sum{ dp(v,0) | v取遍i的所有儿子节点 },如果i不是根节点,那么结果+1,因为i和父亲连接的这条边只被一盏灯照亮。
70 //决策二:节点i处放街灯,dp(i, j) = sum{ dp(v,1) | v取遍i的所有儿子节点 } +M,如果i不是根节点而且j = 0,那么结果 + 1。
71 void build()
72 {
73     scanf("%d%d", &N, &M);
74     for (int i = 0; i<M; ++i)
75     {
76         int a, b;
77         scanf("%d%d", &a, &b);
78         add(a, b);//无向边
79         add(b, a);
80     }
81 }
82 
83 int main()
84 {
85     scanf("%d", &T);//测试用例
86     while (T--)
87     {
88         init();
89         build();
90         for (int i = 0; i<N; ++i) if (!vis[i]) dfs(root = i);//可能有多颗树
91         printf("%d %d %d\n", ans / m, M - ans%m, ans%m);
92     }
93     return 0;
94 }

View Code

1壹 、uva
10817 Headmaster’s Headache ( 状态压缩dp+sstream应用)

  题意:高校现在招老师,给出原来任职的教员职员和工人和前来应聘的教员职员和工人的新闻,求在保障每门科目至少有三个老师教的动静下,最小费用是有点。

  思路:把课程的音信用二进制状态压缩,s1对应还索要2个教育工笔者教的教程,s2对应早就足足老师教的科目.状态设为dp[i][s1][s2]:代表到第i个名师结束,校长最少需求花多少钱达到指标。当i
< m 时,大家必须挑选,状态只能更新为丰硕老师,当i >= m时,
就可以立异为选或不选老师二种状态。s1:当某些学科还亟需二个名师教时,该位记为1,不然记为0;s2:当有些学科已经有丰盛的教师教时,该位记为1,不然记为0。

图片 21图片 22

 1 #include<iostream>
 2 #include<cstring>
 3 #include<string>
 4 #include<sstream>
 5 #include<algorithm>
 6 using namespace std;
 7 const int INF = 0x7f7f7f7f, MAXN = 131;
 8 int s, m, n, teach[MAXN], cost[MAXN], dp[MAXN][1 << 8][1 << 8];
 9 
10 int DP(int i, int s1, int s2)//s1对应还需要一个老师教的科目,s2对应已经足够老师教的科目.状态设为dp[i][s1][s2]:代表到第i个老师为止,校长最少需要花多少钱达到目标。当i < m 时,我们必须选择,状态只能更新为添加老师,当i >= m时, 就可以更新为选或不选老师两种状态。
11 //s1,s2均为2进制数,每一位表示该课程有无老师
12 //s1:当某个学科还需要1个老师教时,该位记为1,否则记为0
13 //s2:当某个学科已经有足够的老师教时,该位记为1,否则记为0
14 {
15     if (i == m + n) return s2 == (1 << s) - 1 ? 0 : INF;  //每个科目都至少两个老师了,那么就不需要再花钱了
16     int &ret = dp[i][s1][s2];//引用
17     if (ret >= 0) return ret;
18     ret = INF;
19     if (i >= m) ret = DP(i + 1, s1, s2);         //不选
20     s2 |= (s1 & teach[i]);                       //老师能教,并且差一个老师,那么一并运算,剩下的就是满足条件的科目
21     s1 |= teach[i];                              //或上去,没人教的科目肯定变成差一个人教
22     ret = min(ret, cost[i] + DP(i + 1, s1, s2)); //选
23     return ret;
24 }
25 
26 int main()
27 {
28     while (~scanf("%d%d%d",&s,&m,&n))
29     {
30         if (s == 0)break;
31         cin.get();
32         string ss;
33         int x;
34         for (int i = 0; i < m + n; ++i)
35         {
36             getline(cin, ss);
37             stringstream sss(ss);
38             sss >> cost[i];
39             teach[i] = 0;
40             while (sss >> x)
41             {
42                 teach[i] |= 1 << (x - 1);
43             }
44         }
45         memset(dp, -1, sizeof dp);
46         //for (int i = 0; i < m + n; ++i) cout << cost[i] << ':' << teach[i] << endl;
47         cout << DP(0, 0, 0) << '\n';
48     }
49     return 0;
50 }

View Code

 12、hdu 1024 Max Sum Plus Plus

  题意:给n个数,未来需求找到m个区间,使得各种区间内成分的和拉长起来最大。

  思路:dp[i][j]表示前j个数在挑选第j个数的前提下分成i段的最大值。dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][k]|(0<k<j))+num[j]);dp[i][j-1]+num[j]代表前j-一个分成i组,j放在别的组里;max(dp[i-1][k]|(0<k<j))+num[j]代表前k个分成i-1组的最大值加上第j个单身成组的深浅。

图片 23图片 24

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n,m;
 5 const int maxn = 1000010;
 6 const int INF = 0x7fffffff;
 7 
 8 int num[maxn];
 9 int dp_now[maxn];
10 int max_pre[maxn];
11 //dp[i][j]表示前j个数在选取第j个数的前提下分成i段的最大值。
12 //dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][k]|(0<k<j))+num[j]);
13 //dp[i][j-1]+num[j]表示前j-1个分成i组,j放在其他组里
14 //max(dp[i-1][k]|(0<k<j))+num[j]表示前k个分成i-1组的最大值加上第j个独立成组的大小
15 int main()
16 {
17     while (~scanf("%d%d", &m, &n))
18     {
19         for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
20         memset(dp_now, 0, sizeof(dp_now));
21         memset(max_pre, 0, sizeof(max_pre));
22         int tmax;
23         for (int i = 1; i <= m; i++)
24         {
25             tmax = -INF;
26             for (int j = i; j <= n; j++)
27             {
28                 dp_now[j] = max(dp_now[j - 1]+num[j], max_pre[j - 1] + num[j]);
29                 max_pre[j - 1] = tmax;
30                 tmax = max(tmax, dp_now[j]);
31             }
32         }
33         printf("%d\n", tmax);
34     }
35     return 0;
36 }

View Code

13、hdu 1029 Ignatius and the Princess
IV

  题意:给出n个数(n为奇数),输出n个数中足足出现(n+1)/2的数。

  思路:扫描一边数组即可。

图片 25图片 26

 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;
 6     while (~scanf("%d", &n))
 7     {
 8         int cal = 0;
 9         int m;
10         int t;
11         while (n--)
12         {
13             scanf("%d", &t);
14             if (cal == 0)
15             {
16                 m = t;
17                 cal++;
18             }
19             else
20             {
21                 if(t != m)
22                 {
23                     cal--;
24                 }
25                 else cal++;
26             }
27         }
28         printf("%d\n", m);
29     }
30 
31 
32 
33     return 0;
34 }

View Code

14、hdu 1069 Monkey and Banana

  题意:给出若干连串型的的砖头,其底面包车型客车长度宽度可由随机两边明确。现在把那个砖块叠放,砖块上方的砖头的底面包车型地铁长和宽都必须低于该砖块的长与宽,求最大惊人。

  思路:先拿走各类砖块各样摆放的艺术,然后按底面长和宽从大到小排序。从小的初叶dp,假诺当前块的长和宽比从前的要大,则拉长。

图片 27图片 28

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 40;
 5 struct node
 6 {
 7     int l;
 8     int w;
 9     int h;
10 }blocks[maxn*6];
11 int dp[maxn * 6];//以i为底的最高高度
12 bool Cmp(const node&a, const node&b)
13 {
14     if (a.l == b.l)return a.w > b.w;
15     else return a.l > b.l;
16 }
17 int main()
18 {
19     int n;
20     int Case = 1;
21     while (~scanf("%d", &n))
22     {
23         if (n == 0)break;
24         int cnt = 0;
25         while (n--)
26         {
27             int xi, yi, zi;
28             scanf("%d%d%d", &xi, &yi, &zi);
29             blocks[cnt].l = xi, blocks[cnt].w = yi, blocks[cnt].h = zi;
30             cnt++;
31             blocks[cnt].l = yi, blocks[cnt].w = xi, blocks[cnt].h = zi;
32             cnt++;
33             blocks[cnt].l = xi, blocks[cnt].w = zi, blocks[cnt].h = yi;
34             cnt++;
35             blocks[cnt].l = zi, blocks[cnt].w = xi, blocks[cnt].h = yi;
36             cnt++;
37             blocks[cnt].l = yi, blocks[cnt].w = zi, blocks[cnt].h = xi;
38             cnt++;
39             blocks[cnt].l = zi, blocks[cnt].w = yi, blocks[cnt].h = xi;
40             cnt++;
41         }
42         sort(blocks, blocks + cnt, Cmp);
43         for (int i = 0; i < cnt; i++) dp[i] = blocks[i].h;
44         for (int i = cnt - 2; i >= 0; --i)
45         {//从小的开始DP
46             for (int j = i + 1; j < cnt; j++)
47             {
48                 if (blocks[j].l < blocks[i].l&&blocks[j].w < blocks[i].w)
49                 {
50                     if (dp[j] + blocks[i].h > dp[i])
51                     {
52                         dp[i] = dp[j] + blocks[i].h;
53                     }
54                 }
55             }
56         }
57         int ans = 0;
58         for (int i = 0; i < cnt; i++)
59         {
60             ans = max(ans, dp[i]);
61         }
62         printf("Case %d: maximum height = %d\n", Case++, ans);
63     }
64 
65 
66     return 0;
67 }

View Code

15、hdu 1074 Doing Homework

  题意:每门功课的作业都有友好的截止日期和做完所需时间。同时,每门功课都有和好学分,假设不能在终结日期前上交作业,每拖一天则多扣二个学分。问最少会扣多少学分。

  思路:科目最多有15门,枚举每门的成就情况,从小到大枚举,假使当前情景st下,要求做到某项作业j,则设想其不需成功该学业的景况stt=st^(1<<j),假若加上那门课后其所扣学分更少,则更新,并记录四驱,以便后续输出。

图片 29图片 30

 1 #include<iostream>
 2 #include<stack>
 3 #include<cstdio>
 4 #include<memory.h>
 5 using namespace std;
 6 int n;
 7 const int maxn = 16;
 8 const int INF = 0x7fffffff;
 9 struct sbj
10 {
11     char nm[110];//科目名称
12     int deadline;//截止日期
13     int cost;//完成需花费的时间
14 }homework[maxn];
15 struct node
16 {
17     int tm;
18     int score;
19     int pre;
20     int now;
21 }dp[1 << maxn];
22 int main()
23 {
24     int t;
25     scanf("%d", &t);
26     while (t--)
27     {
28         scanf("%d", &n);
29         {
30             int total = (1 << n) - 1;
31             for (int i = 0; i < n; i++)
32             {
33                 scanf("%s%d%d", homework[i].nm, &homework[i].deadline, &homework[i].cost);
34             }
35             memset(dp, 0, sizeof(dp));
36             for (int st = 1; st <= total; st++)
37             {//从小的枚举
38                 dp[st].score = INF;
39                 for (int j = n - 1; j >= 0; j--)
40                 {//从最后往前枚举
41                     if (st&(1 << j))
42                     {
43                         int st2 = st ^ (1 << j);
44                         int t = dp[st2].tm + homework[j].cost - homework[j].deadline;
45                         if (t < 0) t = 0;
46                         if (t + dp[st2].score < dp[st].score)
47                         {
48                             dp[st].score = t + dp[st2].score;
49                             dp[st].pre = st2;
50                             dp[st].now = j;
51                             dp[st].tm = dp[st2].tm + homework[j].cost;
52                         }
53                     }
54                 }
55             }
56             printf("%d\n", dp[total].score);
57             int pre = total;
58             stack<int>s;
59             while (pre)
60             {
61                 s.push(dp[pre].now);
62                 pre = dp[pre].pre;
63             }
64             while (!s.empty())
65             {
66                 printf("%s\n", homework[s.top()].nm);
67                 s.pop();
68             }
69         }
70     }
71     return 0;
72 }

View Code

16、hdu 1087  Super Jumping! Jumping!
Jumping!

  题意:以后急需从起源到极限踩格子,每一遍只好前进踩比当下个别大的数字的格子,求所踩格子的数字之和的最大值。

  思路:dp[i]意味着以第i个数结尾的最大上升子类别的和,对于当前的格子i,遍历从前的dp[j](0<=j<=i),如果dp[j]+num[i]>dp[i],则更新dp[i]的值。

图片 31图片 32

 1 #include<iostream>
 2 using namespace std;
 3 const int maxn = 1010;
 4 int num[maxn];
 5 int dp[maxn];//dp[i]代表以第i个数结尾的最大上升子序列的和
 6 int main()
 7 {
 8     int n;
 9     while (~scanf("%d", &n))
10     {
11         if (n == 0) break;
12         for (int i = 0; i < n; i++) scanf("%d", &num[i]);
13         memset(dp, 0, sizeof(dp));
14         dp[0] = num[0];
15         int ans = dp[0];
16         for (int i = 1; i < n; i++)
17         {
18             dp[i] = num[i];
19             for (int j = 0; j <= i; j++)
20             {
21                 if (num[j] < num[i])
22                 {
23                     if (dp[j] + num[i] > dp[i])
24                     {
25                         dp[i] = dp[j] + num[i];
26                     }
27                 }
28             }
29             if (dp[i] > ans) ans = dp[i];
30         }
31         printf("%d\n", ans);
32     }
33     return 0;
34 }

View Code

17、hdu 1114 Piggy-Bank

  题意:给出空的储钱罐的份额和当下储钱罐的份额,给出n种硬币的份量和票面价值。求使得储钱罐内的微小的硬币总价值。

  思路:dp[v] = min(dp[v], dp[v –
coins[i].w] +
coins[i].p);dp[i]意味着硬币总分量为i时,储钱罐内硬币的最低价值。

图片 33图片 34

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn = 510;
 5 const int maxw = 10010;
 6 const int maxp = 50010;
 7 const int INF = 0x7fffffff;
 8 
 9 int dp[maxw];
10 struct coin
11 {
12     int p;
13     int w;
14 }coins[maxn];
15 int main()
16 {
17     int t;
18     scanf("%d", &t);
19     while (t--)
20     {
21         int e, f;
22         scanf("%d%d", &e, &f);
23         int totalw = f - e;//装硬币的重量
24         int minwight = maxw;
25         int n;
26         scanf("%d", &n);
27         for (int i = 0; i < n; i++)
28         {
29             scanf("%d%d", &coins[i].p, &coins[i].w);
30             if (coins[i].w < minwight) minwight = coins[i].w;
31         }
32         if (minwight > totalw)
33         {
34             printf("This is impossible.\n");
35             continue;
36         }
37         for (int i = 0; i <= totalw; i++) dp[i] = INF;
38         dp[0] = 0;
39         for (int i = 0; i < n; i++)
40         {
41             for (int v = 0; v <= totalw; v++)
42             {
43                 if (v - coins[i].w >= 0&& dp[v - coins[i].w]!=INF)
44                 {
45                     /*if(dp[v]>=0)dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);
46                     else dp[v] = dp[v - coins[i].w] + coins[i].p;*/
47                     dp[v] = min(dp[v], dp[v - coins[i].w] + coins[i].p);
48                 }
49             }
50         }
51         if(dp[totalw]<INF)printf("The minimum amount of money in the piggy-bank is %d.\n", dp[totalw]);
52         else
53         {
54             printf("This is impossible.\n");
55         }
56     }
57     return 0;
58 }

View Code

1捌 、HDU 1176 免费馅饼

  题意:天上起初掉馅饼,每秒种只有在运动不当先一米的限制内接住坠落的馅饼。刚初步时站在5的职分,问最终最多能接住多少馅饼。

  思路:从最大日子往前DP。

图片 35图片 36

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<memory.h>
 4 #include<algorithm>
 5 using namespace std;
 6 int n;
 7 const int maxn = 100010;
 8 const int maxt = 100010;
 9 const int INF = 0x7fffffff;
10 int dp[maxt][12];
11 int main()
12 {
13     while (~scanf("%d", &n))
14     {
15         if (n == 0)break;
16         memset(dp,0, sizeof(dp));
17         int maxtt = 0;
18         for (int i = 0; i < n; i++)
19         {
20             int x, t;
21             scanf("%d%d", &x, &t);
22             dp[t][x]++;
23             if (t > maxtt) maxtt=t;
24         }
25         for (int i = maxtt-1; i >= 0; i--)
26         {
27             for (int st = 0; st <= 10; st++)
28             {
29                 if (st == 0) dp[i][st] += max(dp[i + 1][st], dp[i + 1][st + 1]);
30                 else if(st==10)dp[i][st] += max(dp[i + 1][st], dp[i + 1][st - 1]);
31                 else dp[i][st] += max(dp[i + 1][st - 1], max(dp[i + 1][st], dp[i + 1][st + 1]));
32             }
33         }
34         printf("%d\n", dp[0][5]);
35     }
36     return 0;
37 }

View Code

相关文章