#include<iostream>
#include<cstring>
using namespace std;
const int N = 500<<1;
const int INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool vis[N];


int dijkstra(){
    memset(vis,false,sizeof vis);
    memset(dist,INF,sizeof dist);
    dist[1]=0;
    vis[1]=true;
   for(int i=2;i<=n;i++)if(g[1][i])dist[i]=g[1][i];

    for(int i=0;i<n-1;i++){
        int w=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(w==-1||dist[j]<dist[w]))
            w=j;
        }

        vis[w]=true;

        for(int v=1;v<=n;v++){
            if(!vis[v]&&g[w][v]!=0&&dist[w]+g[w][v]<dist[v])
            dist[v]=dist[w]+g[w][v];
        }
    }


    if(dist[n]==INF)return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==b)continue;
        if(!g[a][b])g[a][b]=c;
        else g[a][b]=min(g[a][b],c);
    }

    printf("%d\n",dijkstra());

    return 0;
}

#include<iostream>
#include <cmath>
using namespace std;
const int N = 1e6+10;

int n,cnt;
int st[N];

void get_primes(){
    for(int i=2;i<=n;i++){
        if(st[i])continue;
        cnt++;
        for(int j=i+i;j<=n;j+=i)
        st[j]=true;
    }
}

int main()
{
    scanf("%d", &n);
    get_primes();




    printf("%d\n",cnt);

    return 0;
}

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = N * 2;

int n;
int h[N], e[M], w[M], ne[M], idx;
int ans;

// 添加一条边，a和b是边的两个端点，c是边权
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

// 深度优先搜索，u表示当前节点，father表示当前节点的父节点
// 返回值表示从当前节点往下走的最大长度
int dfs(int u, int father)
{
    int dist = 0; // 表示从当前点往下走的最大长度
    int d1 = 0, d2 = 0;

    // 遍历当前节点的所有孩子节点
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        // 如果孩子节点是当前节点的父节点，则跳过

        if (j == father) continue;
        // 递归遍历孩子节点，并计算从孩子节点往下走的最大长度
        int d = dfs(j, u) + w[i];
        // 更新从当前节点往下走的最大长度
        dist = max(dist, d);

        // 维护当前节点的最长路径d1和次长路径d2
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }

    // 计算当前节点的直径，并更新全局最大值ans
    ans = max(ans, d1 + d2);

    // 返回从当前节点往下走的最大长度
    return dist;
}

int main()
{
    cin >> n;

    memset(h, -1, sizeof h);
    // 读入所有边，建立树的邻接表
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    // 从根节点开始进行深度优先搜索
    dfs(1, -1);

    // 输出树的直径
    cout << ans << endl;

    return 0;
}

太难了
#include<iostream>
#include<cstring>
using namespace std;
const int N = 6e3+10;
int happy[N];
int h[N],e[N],nxt[N],cur;
bool has_father[N];
int f[N][2];

void add(int a,int b){
    e[cur]=b;
    nxt[cur]=h[a];
    h[a]=cur++;
}


void dfs(int u){
    f[u][1]=happy[u];

    for(int i=h[u];i!=-1;i=nxt[i]){
        int j=e[i];

        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=f[j][0];
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)scanf("%d",happy+i);

    for(int i=1;i<=n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(b,a);
        has_father[a]=true;
    }

    int root=1;
    while(has_father[root])root++;

    dfs(root);

    printf("%d\n",max(f[root][0],f[root][1]));

    return 0;
}

#include<iostream>
using namespace std;
const int N = 310;
int a[N],f[N][N];


int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),a[i]+=a[i-1];

    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;

            f[i][j]=1e9;
            for(int k=i;k<j;k++)
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
        }
    }
    printf("%d\n",f[1][n]);

    return 0;
}

#include<iostream>
using namespace std;
const int N = 310;
int a[N],f[N][N];


int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),a[i]+=a[i-1];

    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;

            f[i][j]=1e9;
            for(int k=i;k<j;k++)
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
        }
    }
    printf("%d\n",f[1][n]);

    return 0;
}

真的很难。。。。




#include<iostream>
using namespace std;
const int N = 1e3+10;

int n,m;
char s[N],t[N];
int f[N][N];

int main()
{
    cin>>n>>s+1>>m>>t+1;


    //初始化
    for(int i=0;i<=n;i++)f[i][0]=i;
    for(int i=0;i<=m;i++)f[0][i]=i;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=min(f[i-1][j],f[i][j-1])+1;
            if(s[i]==t[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }

    printf("%d\n",f[n][m]);


    return 0;
}

{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d",s+i);
    for(int i=1;i<=n;i++)scanf("%d",t+i);


    int res=0;
    for(int i=1;i<=n;i++){
        int maxv=1;
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][j];
            if(s[i]==t[j])f[i][j]=max(maxv,f[i][j]);
            if(t[j]<s[i])maxv=max(maxv,f[i-1][j]+1);
        }
    }

    for(int i=1;i<=n;i++)res=max(res,f[n][i]);
    printf("%d",res);

    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>
#include<string>
using namespace std;
const int N = 1e3+10;

int f[N][N];
char s[N],t[N];

int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    cin>>s+1>>t+1;


    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
        f[i][j]=max(f[i-1][j],f[i][j-1]);
        if(s[i]==t[j])
        f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m]<<endl;

    return 0;

}

还是比较简单

#include<iostream>
using namespace std;
const int N = 1e3+10;

int a[N],f[N];


int main()
{
    int n;
    int res=0;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d",a+i),f[i]=1;


    for(int i=1;i<=n;i++){
      for(int j=i-1;j;j--){
          if(a[i]<=a[j])continue;
          if(f[i]<f[j]+1)f[i]=f[j]+1;
      }
      res=max(f[i],res);
    }

    printf("%d\n",res);
    return 0;
}