当前位置：首页 > news >正文

Section 1.5 也许这才是暴力搜索

news 来源：原创 2024/4/28 5:18:21

Number Triangles

经典DP。

自控老师曾经用了一节课讲这道题。。我以为我早就懂了，居然听不懂那一堆奇怪的公式。果然自控是天书。

#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
int f[N][N], dp[N][N];
int main()
{

    freopen("numtri.in","r",stdin);
    #ifndef poi
    freopen("numtri.out","w",stdout);
    #endif
    int n, i, j;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        for(j = 1; j <= i; j++) scanf("%d", &f[i][j]);
    }
    for(i = n; i >= 1; i--){
        for(j = 1; j <= i; j++){
            dp[i][j] = max(dp[i][j], max(dp[i+1][j], dp[i+1][j+1])+f[i][j]);
        }
    }
    cout << dp[1][1]<<endl;
    return 0;
}

View Code

Prime Palindromes

找出[a,b]区间内所有回文的素数

还没从简单题的气氛里醒过了，一开始以为爆搞，看了下数据范围= =

思考了一下，奇数偶数长度一起搞有一些麻烦，想分开来搞，后来感受到了。。

小学奥数姿势：怎么看出一个数是不是11的倍数。可以发现偶数长度的一定是11的倍数，所以只有11是可行的。

这样就处理一下奇数长度就好了。

DFS一下，然后判断。

#include <bits/stdc++.h>
using namespace std;

vector<int>v;
int factor[13];
bool isprime(int x){
    int m = sqrt(x) + 1;

    for(int i = 2; i <= m; i++){
        if(x % i == 0)   return false;
    }
    return true;
}
void dfs(int len, int now){
    if(len >= 8) return;
    if(isprime(now)){
        v.push_back(now);

    }

    for(int i = 0; i <= 9; i++){
        dfs(len + 2, now * 10 + factor[len]*i+i);
    }
}
int main()
{
    freopen("pprime.in","r",stdin);
    #ifndef poi
    freopen("pprime.out","w",stdout);
    #endif
    int a, b, i;
    cin >> a>> b;
    factor[1] = 100;

    for(i = 2; i <= 7; i++) factor[i] = factor[i-1]*10;

    for(i = 0; i <= 9; i++){
        dfs(1, i);
    }
    v.push_back(11);
    sort(v.begin(), v.end());

    for(i = 0; i < v.size(); i++){
        if(v[i] >= a && v[i] <= b)  printf("%d\n", v[i]);
    }
    return 0;
}

View Code

Superprime Rib

对于一个N位数，使得前1,2,3，。。。N位都是素数

爆搜

#include <bits/stdc++.h>
using namespace std;
vector<int>v;
int n;

bool isprime(int x){
    int m = sqrt(x);

    for(int i = 2; i <= m; i++){
        if(x % i == 0)   return false;
    }
    return true;
}
void dfs(int len, int now){
    if(len == n){
        v.push_back(now);
        return;
    }

    for(int i = 0; i <= 9; i++){
        if(isprime(now * 10 + i))   dfs(len + 1, now * 10 + i);
    }
}
int main()
{
    freopen("sprime.in","r",stdin);
    #ifndef poi
    freopen("sprime.out","w",stdout);
    #endif
    cin >> n;
    for(int i = 2; i <= 9; i++){
        if(isprime(i)) dfs(1, i);
    }
    for(int i = 0; i < v.size(); i++){
        printf("%d\n", v[i]);
    }
    return 0;
}