文档章节

3月13号周练——2015 Multi-University Training Contest 9

YYQ_ZJL
 YYQ_ZJL
发布于 2016/07/03 10:33
字数 541
阅读 0
收藏 0

2015 Multi-University Training Contest 9

A. Expression(理解原理 区间DP

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define maxn 105
#define mod 1000000007
using namespace std;
long long dp[maxn][maxn];
long long A[maxn],C[maxn][maxn];
char operations[maxn];
int a[maxn],n;
/*初始化从0到maxn的阶乘模mod*/
void init()
{
    int i,j;
    A[0] = 1;
    for(i = 1;i < maxn; i++)
    {
        A[i] = (A[i-1]*i)%mod;
    }
    C[0][0] = 1;
    for(i=1; i<=100; i++)
    {
        C[i][0] = 1;
        for(j=1; j<=i; j++)
            C[i][j] = (C[i-1][j-1] + C[i-1][j])%mod;
    }
}
void solve()
{
    int len,l,r,k;
    for(l = 1;l <= n;l ++)
        dp[l][l] = a[l];
    for(len = 2;len <= n;len ++)
    {
        for(l = 1;l + len - 1 <= n; l ++)
        {
            long long t;
            r = l + len -1;
            for(k = l;k < r;k ++)
            {
                if(operations[k] == '+'){
                    t = (dp[l][k]*A[r-k-1] + dp[k+1][r]*A[k-l])%mod;
                }
                else if(operations[k] == '-'){
                    t = (dp[l][k]*A[r-k-1] - dp[k+1][r]*A[k-l])%mod;
                }
                else{
                    t = (dp[l][k]* dp[k+1][r])%mod;
                }
                dp[l][r] = (dp[l][r] + t* C[r-l-1][k-l])%mod;
            }
        }
    }
}
int main()
{
    init();
    while(cin >> n)
    {
        memset(dp, 0, sizeof(dp));
        int i,j;
        for(i = 1;i <= n;i ++){
            cin >> a[i];
        }
        for(i = 1;i < n;i ++){
            cin >> operations[i];
        }
        solve();
        cout << (dp[1][n]+mod)%mod << endl;              //此段代码借鉴的,为什么?
    }
    return 0;
}

小结:此题看过题解后,思路是对的,但是对取模的机制和组合数的求法不是很熟练,需要加强。

Travelling Salesman Problem

#include <iostream>
#include<cstdio>
#define maxn 105
#define black 1
#define white 0
using namespace std;
int n,m;
long long sum,min;
int map[maxn][maxn],color[maxn][maxn];    //color[][] = 0/1,1代表白色,0代表黑色
void init()
{
    int i ,j;
    bool tmp = true;
    for(i = 1;i <= n;i ++)
    {
            for(j = 1;j <= m;j ++)
            {
                    if(tmp)
                        color[i][j] = black;
                    else
                        color[i][j] = white;
                    tmp = !tmp;
            }
    }
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
            init();
            sum = 0;
            int i,j;
            for(i = 1;i <= n;i ++)
            {
                for(j = 1;j <= m;j ++)
                {
                    scanf("%d",&map[i][j]);
                    sum += map[i][j];
                }
            }
                /*行数n为奇数*/
                if(n%2!=0)
                {
                    printf("%lld\n",sum);
                    for(i = 1;i <= n;i ++)
                    {
                        if(i%2 != 0)
                        {
                            for(j = 1;i < m;i ++)
                                printf("R");
                        }
                        else
                        {
                                printf("D");
                                for(j= 1;j < m;j ++)
                                        printf("L");
                        }
                    }
                }
                /*行数为偶数,但列数为奇数*/
                else if(m%2 !=  0)
                {
                        printf("%lld\n",sum);
                        for(i = 1;i <= m;i ++)
                        {
                                if(i%2 != 0)
                                {
                                        for(j = 1;i < n;i ++)
                                        printf("D");
                                }
                                else
                                {
                                        printf("L");
                                        for(j= 1;j < n;j ++)
                                                printf("U");
                                }
                        }
                }
                /*行列都为偶数*/
                else
                {
                        
                }
        }
        return 0;
}

 

本文转载自:http://www.cnblogs.com/zhangjialu2015/p/5272208.html

YYQ_ZJL
粉丝 0
博文 30
码字总数 206
作品 0
杭州
其他
私信 提问
HDU3605: Escape-二进制优化建图-最大流

目录 目录 思路: (有任何问题欢迎留言或私聊 && 欢迎交流讨论哦 目录 题意:传送门  原题目描述在最下面。  (n(nleq 100000))个人(m(mleq 10))个星球,每个星球容纳的人数有上限,每个人...

Cwolf9
2018/08/04
0
0
HDU 3487 Play with Chain

Problem Description YaoYao is fond of playing his chains. He has a chain containing n diamonds on it. Diamonds are numbered from to . At first, the diamonds on the chain is a se......

wang3312362136
2018/01/10
0
0
2017 多校训练第二场 HDU 6047 Maximum Sequence(贪心+优先队列)

Maximum SequenceTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2404 Accepted Submission(s): 1131 Problem Description Steph......

Timeclimber
2017/12/13
0
0
每周一练 之 数据结构与算法(Tree)

这是第六周的练习题,最近加班比较多,上周主要完成一篇 GraphQL入门教程 ,有兴趣的小伙伴可以看下哈。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据...

pingan8787
05/20
0
0
【暑期集训第一场】欧拉回路 | 思维 | 数论构造 | 容斥原理 | 线段树 | 归并排序

集训1(HDU2018 Multi-University Training Contest 2) ID A B C D E F G H I J AC O O 补题 ? O ? O 代码 & 简易题解 [A]:期望? 神仙题,留坑.. [B]:?? 同(text{A}) [C]:求欧拉通路条...

_403Forbidden
08/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Giraph源码分析(八)—— 统计每个SuperStep中参与计算的顶点数目

作者|白松 目的:科研中,需要分析在每次迭代过程中参与计算的顶点数目,来进一步优化系统。比如,在SSSP的compute()方法最后一行,都会把当前顶点voteToHalt,即变为InActive状态。所以每次...

数澜科技
今天
4
0
Xss过滤器(Java)

问题 最近旧的系统,遇到Xss安全问题。这个系统采用用的是spring mvc的maven工程。 解决 maven依赖配置 <properties><easapi.version>2.2.0.0</easapi.version></properties><dependenci......

亚林瓜子
今天
10
0
Navicat 快捷键

操作 结果 ctrl+q 打开查询窗口 ctrl+/ 注释sql语句 ctrl+shift +/ 解除注释 ctrl+r 运行查询窗口的sql语句 ctrl+shift+r 只运行选中的sql语句 F6 打开一个mysql命令行窗口 ctrl+l 删除一行 ...

低至一折起
今天
9
0
Set 和 Map

Set 1:基本概念 类数组对象, 内部元素唯一 let set = new Set([1, 2, 3, 2, 1]); console.log(set); // Set(3){ 1, 2, 3 } [...set]; // [1, 2, 3] 接收数组或迭代器对象 ...

凌兮洛
今天
4
0
PyTorch入门笔记一

张量 引入pytorch,生成一个随机的5x3张量 >>> from __future__ import print_function>>> import torch>>> x = torch.rand(5, 3)>>> print(x)tensor([[0.5555, 0.7301, 0.5655],......

仪山湖
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部