ACM程序设计_期末考试

HDU Today_Dijkstra

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define MAX 2100 
int INF = 99999999,n;
int e[MAX][MAX],d[MAX];
bool visit[MAX];
map <string,int>mm;
string a,b,s,aend;
int c,k=1;

void dijkstra(){
    fill(d,d+k+1,INF);
    fill(visit,visit+k,false);
    d[1]=0;
    while(true){
        int v=-1;
        for(int u=1;u<=k;u++){//这里千万不能是n 
            if(!visit[u]&&(v==-1||d[u]<d[v])){
                v=u;
            }
        }
        if(v==-1){
            break;
        }
        visit[v]=true;
        for(int u=1;u<=k;u++){
            if(!visit[u]&&e[v][u]!=INF){
                if(d[u]>d[v]+e[v][u]){
                    d[u]=d[v]+e[v][u];
                }
            }
        }
    }
}

int main(){
    while(cin>>n&&n!=-1){
        mm.clear();
        cin>>s>>aend;
        //用map映射给站名标记，起始站为1，终点站为2
        //怪不得之前的代码总是bug
        k=1;//这里忘记初始化，every time 卡了那么久，原来是在这里
        mm[s]=k++;
        mm[aend]=k++;
        //初始化e 
        for(int i=0;i<155;i++){
            for(int j=0;j<155;j++){
                if(i==j)
                    e[i][j]=0;
                else
                    e[i][j]=INF;
            }
        }
        for(int i=1;i<=n;i++){
            cin>>a>>b>>c;
            if(!mm[a])
                mm[a]=k++;
            if(!mm[b])
                mm[b]=k++;
            if(c<e[mm[a]][mm[b]])
                e[mm[a]][mm[b]]=e[mm[b]][mm[a]]=c;
        }   
        if(s==aend)
            cout<<"0"<<endl;
        else{
            dijkstra();
            if(d[2]==INF)
                cout<<"-1"<<endl;
            else
                cout<<d[2]<<endl;
        }       
    }
    return 0;
}

Saving HDU_贪心 分组背包

贪心做法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[101][101];//,pi[101],m[101];
struct so{
    int pi;
    int m;
}s[101];

bool cmp(struct so &a, struct so &b){
    return a.pi>b.pi;
}

int main(){
    int v,n;
    while(cin>>v&&v!=0){
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>s[i].pi>>s[i].m;
        sort(s,s+n,cmp);
        int sum=0;
        for(int i=0;i<n;i++){
            if(v-s[i].m>0){
                sum+=s[i].m*s[i].pi;
                v-=s[i].m;
            }
            else{
                sum+=v*s[i].pi;
                break;
            }
        }
        cout<<sum<<endl;
    } 
    return 0;
}

分组背包做法

当时做dp训练时居然忘了分组背包

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[101],pi[101],m[101];

int main(){
    int v,n;
    while(cin>>v&&v!=0){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>pi[i]>>m[i];
        }   
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=v;j>=0;j--){
                for(int k=1;k<=m[i];k++){
                    int t1=k,t2=k*pi[i];
                    if(j<k)
                        continue;
                    dp[j]=max(dp[j],dp[j-t1]+t2);
                }
            }
        }
        cout<<dp[v]<<endl;
    }
    return 0;
}

Crisis of HDU_母函数

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,pi[101],m[101],a[10000],b[10100];

int main(){
    while(cin>>n&&n){
        memset(pi,0,sizeof(pi));
        memset(m,0,sizeof(m));
        int sum=0;
        for(int i=0;i<n;i++){
            cin>>pi[i]>>m[i];
            sum+=pi[i]*m[i];
        }
        if(sum%3){
            cout<<"sorry"<<endl;
            continue;
        }
        sum/=3;
        memset(a,0,sizeof(a));
        a[0]=1;
        int before=0;
        int _next;
        for(int i=0;i<n;i++){
            _next=min(before+pi[i]*m[i],sum);
            memset(b,0,sizeof(int)*(_next+1));
            for(int j=0;j<=m[i]&&j*pi[i]<=_next;j++){
                for(int k=0;k<=before&&k+j*pi[i]<=_next;k++){
                    b[k+j*pi[i]]+=a[k];
                    b[k+j*pi[i]]%=10000;
                }
            }
            memcpy(a,b,sizeof(int)*(_next+1));
            before=_next;
        } 
        if(a[sum]>0)
            cout<<a[sum]<<endl;
        else
            cout<<"sorry"<<endl;
    }
    return 0;
}