Wannafly Union #5(c.dp,d.dijkstra)

原题链接：https://vjudge.net/contest/148523#overview

B - Cow Multiplication

题目

Paste_Image.png

分析

新定义一种乘法规则，然后给你两个数让你算。用字符串读入然后直接模拟过程就好。

ac代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;
string a, b;
int main(){
    cin >> a >> b;
    int ans = 0;
    for(int i = 0; i < a.size(); ++i){
        for(int j = 0; j < b.size(); ++j){
            ans += ((a[i] - '0') * (b[j] - '0'));
        }
    }
    cout << ans << endl;
    return 0;
}

C - Treats for the Cows

题目

Paste_Image.png
Paste_Image.png

分析

给你一组数，只能从两边取，每次取得到的钱为数的value * （第几次的次数），然后让你求最大能得到多少钱。一开始想贪心，但并没有想到好的贪法，只能老老实实的动态规划做喽。
开一个（long long）n*n的数组记录dp状态。
dp[i][j] = max(dp[i][j], dp[i - 1][j] + (n - (j - i + 1)) * a[i - 1]);
dp[i][j] = max(dp[i][j], dp[i][j + 1] + (n - (j - i + 1)) * a[j + 1]);

ac代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#define inf 1e17
typedef long long ull; 
using namespace std;
const int maxn = 2e3 + 5;
int a[maxn], n;
ull dp[maxn][maxn];
void init(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", a + i);
    }
}
void solve(){
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < n; ++i){
        for(int j = n - 1; j >= i; --j){
            if(i > 0){
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + (n - (j - i + 1)) * a[i - 1]);
            }
            if(j < n - 1){
                dp[i][j] = max(dp[i][j], dp[i][j + 1] + (n - (j - i + 1)) * a[j + 1]);
            }
        }
    }
    ull ans = 0;
    /*for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            printf("%lld ", dp[i][j]);
        }
        cout << endl;
    }*/
    for(int i = 0; i < n; ++i){
        ans = max(ans, dp[i][i] + a[i] * n);
    }
    printf("%lld", ans);
}
int main(){
    init();
    solve();
    return 0;
}

D - Silver Cow Party

题目

Paste_Image.png
Paste_Image.png

分析

给一个有向图，指定一个点，让求所有点到该点的最短路再回去的最短路花费的和的最大值。
一开始我直接floyd-warshall跑t了，改成两边dijkstra就好了，一边正的，一边反的，然后遍历求解。
这个题写的时候有点急，代码写的好丑。

ac代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
typedef long long ull; 
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 1e3 + 5;
const int maxm = 1e5 + 5;
int road[maxn][maxn], n, m, x;
int d1[maxn], d2[maxn];
bool used[maxn];
void solve(){
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            road[i][j] = inf;
            if(i == j) road[i][j] = 0;
        }
    }
    for(int i = 0; i < m; ++i){
        int t1, t2, t3;
        scanf("%d%d%d", &t1, &t2, &t3);
        road[t1][t2] = t3;
    }
/*  for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            printf("%11d", road[i][j]);
        }
        printf("\n");
    }*/
    fill(d1 + 1, d1 + n + 1, inf);
    fill(d2 + 1, d2 + n + 1, inf);
    memset(used, 0, sizeof(used));
    d1[x] = 0;
    while(1){
        int v = -1;
        for(int u = 1; u <= n; ++u){
            if(!used[u] && (v == -1 || d1[u] < d1[v])) v = u;
        } 
        if(v == -1) break;
        used[v] = 1;
        for(int u = 1; u <= n; ++u){
            //printf("%d: %d\n", u, d1[u]);
            d1[u] = min(d1[u], d1[v] + road[v][u]);
            //printf("%d: %d\n", u, d1[u]);
        }
    }
    memset(used, 0, sizeof(used));
    d2[x] = 0;
    while(1){
        int v = -1;
        for(int u = 1; u <= n; ++u){
            if(!used[u] && (v == -1 || d2[u] < d2[v])) v = u;
        } 
        if(v == -1) break;
        used[v] = 1;
        for(int u = 1; u <= n; ++u){
            d2[u] = min(d2[u], d2[v] + road[u][v]);
        }
    }
    
/*  for(int i = 1; i <= n; ++i){
        printf("%d %d\n", d1[i], d2[i]);
    }*/
    
    
    
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, d1[i] + d2[i]);
    }
    cout << ans << endl;
}
int main(){
    solve();
    return 0; 
}

E - The Moronic Cowmpouter

题目

Paste_Image.png

分析

把一个树转换成-2进制，刚看到题一脸懵逼，后来找找就发现可以找规律，用一个num[]数组去记录位数，
1 = 1
2 = -2 + 4
4 = 4
...
-1 = 1 - 2
-2 = -2
-4 = 4 - 8
...
然后num数组并不一定是个都是1和0的数组，需要进位，进位的标准是
if(num[i] > 1)
则num[i] -= 2; ++num[i+1]; ++num[i+2];
完美ac。

ac代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
typedef long long ull; 
using namespace std;
int n;
int num[60];
void print_ans(){
    //cout << " 1" << endl;
    for(int i = 0; i < 60; ++i){
        while(num[i] > 1){
            num[i] -= 2;
            ++num[i + 1];
            ++num[i + 2];
        }
    }
    int text = 1;
    for(int i = 60 - 1; i >= 0; --i){
        if(!text){
            printf("%d", num[i]);
        }
        else{
            if(num[i] != 0){
                text = 0;
                printf("%d", num[i]);
            }
        }
    }
}
int main(){
    cin >> n;
    if(n == 0){
        printf("0");
    }
    else if(n >= 0){
        memset(num, 0, sizeof(num));
        int i = 0;
        while(n != 0){
            if(n % 2 != 0){
                if(i % 2 == 0){
                    ++num[i];
                }
                else {
                    ++num[i];
                    ++num[i + 1];
                }
            }
            n /= 2;
            ++i;
        }
        print_ans();
    }
    else{
        memset(num, 0, sizeof(num));
        int i = 0;
        while(n != 0){
            if(n % 2 != 0){
                if(i % 2 != 0){
                    ++num[i];
                }
                else {
                    ++num[i];
                    ++num[i + 1];
                }
            }
            n /= 2;
            ++i;
        }
        print_ans();
    }
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • LeetCode/LintCode ReviewPage 题解-总结
    背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcod...
    土汪阅读 14,353评论 0赞 33
  • Java初级面试题
    1. Java基础部分 基础部分的顺序：基本语法，类相关的语法，内部类的语法，继承相关的语法，异常的语法，线程的语...
    子非鱼_t_阅读 32,116评论 18赞 399
  • C基础算法
    C语言的学习要从基础开始，这里是100个经典的算法－１C语言的学习要从基础开始，这里是100个经典的 算法 题目：...
    Poison_19ce阅读 4,929评论 0赞 0
  • Dynamic Programming-动态规划(偶尔更新)
    （欢迎转载，但请注明出处并附带链接）算法好久没复习了，今天看见一妹子在办公室刷Leetcode，顿时我也来了兴趣，...
    Nick_Zuo阅读 3,911评论 0赞 3
  • 和台湾的相识相知“半月谈”
    台北：初见倾心 D1 其实严格意义上讲，这不算是第一天。傍晚六点从宝安机场登机，两个多小时后到达台北桃园机场。尽管...
    Emma1962阅读 3,899评论 0赞 0