poj1661 Help Jimmy

发表于 2020-05-22 分类于算法， ACM

题意

是男人就下一百层！你有初始的x坐标与高度下面有n块板子每个板子都有自己的长度与高度你下降与在板子上走的速度都是1m/s，你唯一能做的操作是掉落到板子上时候选择向左走还是向右走，问掉到地面的最短时间保证有解

另外你每次掉落的高度不能超过一个max值，超过就摔死了~

题解

写起来要稍稍复杂一些。。简单来说我的思路是dp[i][j]表示走到第i块板子的边缘所需要的时间，j为0或1，首先把板子按高度排一下，然后对于每块板子看在它之前的板子能不能掉到它上，统计一下走到边缘花的时间，最后遍历找最小即可

实际上问题要稍稍复杂一些。。因为掉落是没办法控制的，也就是说你从边缘掉下去而下面有板子你就一定会掉上去需要再走到边缘而不能传过去（所以加了一个记录来判断这个问题

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=0x3f3f3f3f;
int dp[1020][2];
struct wal{
    int x[2];
    int h;
    int ans[2];
    int next[2];
};
wal walls[1020];
bool cmp(wal a,wal b){
    return a.h>b.h;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,x,y,hmax;
        scanf("%d%d%d%d",&n,&x,&y,&hmax);
        for(int i=1;i<=n;++i){
            scanf("%d%d%d",&walls[i].x[0],&walls[i].x[1],&walls[i].h);
        }
        walls[0].x[0]=walls[0].x[1]=x;
        walls[0].h=y;
        sort(walls+1,walls+1+n,cmp);
        memset(dp,MAXN,sizeof(dp));
        dp[0][0]=dp[0][1]=0;
        int ans=MAXN;
        for(int i=0;i<=n;++i){
            walls[i].ans[0]=walls[i].ans[1]=MAXN;
            walls[i].next[0]=walls[i].next[1]=-1;
            for(int j=0;j<i;++j){
                if((walls[j].h-walls[i].h)>hmax){
                    continue;
                }
                if(dp[j][0]!=MAXN&&walls[j].x[0]>=walls[i].x[0]&&walls[j].x[0]<=walls[i].x[1]&&walls[j].next[0]==-1){
                    walls[j].next[0]=i;
                    dp[i][0]=min(dp[i][0],dp[j][0]+walls[j].h-walls[i].h+abs(walls[j].x[0]-walls[i].x[0]));
                    dp[i][1]=min(dp[i][1],dp[j][0]+walls[j].h-walls[i].h+abs(walls[j].x[0]-walls[i].x[1]));
                }
                if(dp[j][1]!=MAXN&&walls[j].x[1]>=walls[i].x[0]&&walls[j].x[1]<=walls[i].x[1]&&walls[j].next[1]==-1){
                    walls[j].next[1]=i;
                    dp[i][0]=min(dp[i][0],dp[j][1]+walls[j].h-walls[i].h+abs(walls[j].x[1]-walls[i].x[0]));
                    dp[i][1]=min(dp[i][1],dp[j][1]+walls[j].h-walls[i].h+abs(walls[j].x[1]-walls[i].x[1]));
                }
            }
            if(walls[i].h<=hmax){
                walls[i].ans[0]=min(walls[i].ans[0],dp[i][0]+walls[i].h);
                walls[i].ans[1]=min(walls[i].ans[1],dp[i][1]+walls[i].h);
            }
        }
        for(int i=0;i<=n;++i){
            if(walls[i].next[0]==-1){
                ans=min(ans,walls[i].ans[0]);
            }
            if(walls[i].next[1]==-1){
                ans=min(ans,walls[i].ans[1]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj1458 Common Subsequence

发表于 2020-05-21 分类于算法， ACM

题意

。。最长公共子序列简单易懂的题面

题解

。。基础dp 没啥说的。。不过看了一下还是有优化的思路可以找到第一个序列在第二个序列中的出现位置，这样出现位置的序列来做最长上升子序列利用二分在理论上可以到O(nlogn)的复杂度不过依旧是懒得实践（

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[1200][1200];
char x[1200],y[1200];
int main(){
    while(~scanf("%s%s",x,y)){
        memset(dp,0,sizeof(dp));
        int i,j;
        for(i=0;x[i]!='\0';++i){
            for(j=0;y[j]!='\0';++j){
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                if(x[i]==y[j]){
                    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
                }
            }
        }
        printf("%d\n",dp[i][j]);
    }
    return 0;
}

poj1015 Jury Compromise

发表于 2020-05-20 分类于算法， ACM

题意

简单来说，从n个人中挑m个人，每个人有两个评分，要求令评分差绝对值最小，评分差绝对值最小的情况下找总评分最大的

题解

这道题。。细节很多。。思路很简单的dp，dp[i][j]表示选了i个人评分差之和的绝对值为j，更新的方程就显而易见了，从i-1个人中可能的情况向后更新，这里面有不少问题，一个是你要怎么判断这个人有没有被选中，实际上考虑到这个数据量。。直接搜索即可，另外要注意一定找遍整个路径，不然的话很多数据更新时候的问题。。第二个是dp的顺序，一开始我是按每个人遍历整个dp数组然后下一个人，但是这样会导致一个人被反复用的情况。。所以我换了一下思路。。第二个要输出选的人升序输出。。反正输出格式化是蛮费事的。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct people{
    int score[2],sum,sub;
}person[230];
int dp[22][820],last[22][820];
void input(int i){
    scanf("%d%d",&person[i].score[0],&person[i].score[1]);
    person[i].sub=person[i].score[0]-person[i].score[1];
    person[i].sum=person[i].score[0]+person[i].score[1];
}
bool select(int j,int t,int i){
    while(last[j][t]!=-1){
        if(last[j][t]==i){
            return false;
        }
        t-=person[last[j][t]].sub;
        j--;
    }
    return true;
}
int main(){
    int n,m;
    int T=1;
    while(scanf("%d%d",&n,&m),n+m){
        memset(dp,-1,sizeof(dp));
        memset(last,-1,sizeof(last));
        dp[0][400]=0;
        for(int i=0;i<n;++i){
            input(i);
        }
        for(int j=0;j<m;++j){
            for(int i=0;i<n;++i){
                for(int t=0;t<=800;++t){
                    if(dp[j][t]!=-1&&select(j,t,i)){
                        if((dp[j][t]+person[i].sum)>dp[j+1][t+person[i].sub]){
                            dp[j+1][t+person[i].sub]=dp[j][t]+person[i].sum;
                            last[j+1][t+person[i].sub]=i;
                        }
                    }
                }
            }
        }
        int ansmax=0,res[2]={0,0},ans;
        bool find=false;
        for(int i=0;i<=400;++i){
            if(dp[m][400+i]!=-1){
                ansmax=dp[m][400+i],ans=400+i;
                find=true;
            }
            if(dp[m][400-i]!=-1){
                if(dp[m][400-i]>ansmax){
                    ansmax=dp[m][400-i],ans=400-i;
                    find=true;
                }
            }
            if(find){
                break;
            }
        }
        int index=m;
        vector<int> resque;
        while(last[index][ans]!=-1){
            int i=last[index][ans];
            resque.push_back(i);
            res[0]+=person[i].score[0],res[1]+=person[i].score[1];
            index--,ans-=person[i].sub;
        }
        sort(resque.begin(),resque.end());
        printf("Jury #%d\n",T);
        T++;
        printf("Best jury has value %d for prosecution and value %d for defence:\n",res[0],res[1]);
        for(int i=0;i<resque.size();++i){
            printf(" %d",resque[i]+1);
        }
        printf("\n\n");
    }
    return 0;
}

hdu1160 FatMouse's Speed

发表于 2020-05-18 分类于算法， ACM

题意

给n个老鼠，有各自的重量和速度，要找到一个体重严格上升，速度严格下降的最长排列

题解

实际就是LIS 条件变一下，我用了一个之前图的思路来求也勉强算是记忆化搜索吧。。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int W[1020],S[1020],length[1020],nextm[1020];
vector<int> G[1020];
bool find_mat(int a,int b){
    return W[a]>W[b]&&S[a]<S[b];
}
int dfs(int x){
    if(length[x]!=-1){
        return length[x]+1;
    }
    length[x]=0;
    for(int i=0;i<G[x].size();++i){
        int tmp=dfs(G[x][i]);
        if(tmp>length[x]){
            length[x]=tmp;
            nextm[x]=G[x][i];
        }
    }
    return length[x]+1;
}
int main(){
    int n=0;
    memset(nextm,-1,sizeof(nextm));
    memset(length,-1,sizeof(length));
    while(~scanf("%d%d",&W[n],&S[n])){
        ++n;
        for(int i=0;i<(n-1);++i){
            if(find_mat(i,n-1)){
                G[n-1].push_back(i);
            }
            if(find_mat(n-1,i)){
                G[i].push_back(n-1);
            }
        }
    }
    int res=-1,ans=0;
    for(int i=0;i<n;++i){
        if(dfs(i)>ans){
            ans=length[i]+1;
            res=i;
        }
    }
    printf("%d\n%d\n",ans,res+1);
    while(nextm[res]!=-1){
        printf("%d\n",nextm[res]+1);
        res=nextm[res];
    }
    return 0;
}

hdu1257 最少拦截系统

发表于 2020-05-17 分类于算法， ACM

题目大意

拦截导弹，每次拦截的高度不能大于上一次，对于给定序列需要几套拦截系统

题解

简单的。。最长上升子序列。。懒得加二分优化了。。数据量太水了导致优不优化。。差别不大

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[30030];
const int MAXN=0x3f3f3f3f;
int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(dp,MAXN,sizeof(dp));
        int res=0,last=0,tmp;
        for(int i=0;i<n;++i){
            scanf("%d",&tmp);
            int j=0;
            while(dp[j]<tmp){
                ++j;
            }
            dp[j]=tmp;
        }
        for(res=0;res<n;++res){
            if(dp[res]!=MAXN){
                continue;
            }
            break;
        }
        printf("%d\n",res);
    }
    return 0;
}

hdu1260 Tickets

发表于 2020-05-17 分类于算法， ACM

题意

k个人买票每个人有自己买票的时长，任意两个相邻的人有一块买票的时长问最短耗时

题解

。。基本DP
dp[i]=min(dp[i-1]+si[i],dp[i-2]+adi[i])

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[2020],adi[2020],si[2020];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int k;
        scanf("%d",&k);
        for(int i=1;i<=k;++i){
            scanf("%d",&si[i]);
        }
        for(int i=2;i<=k;++i){
            scanf("%d",&adi[i]);
        }
        dp[0]=0;
        dp[1]=si[1];
        for(int i=2;i<=k;++i){
            dp[i]=min(dp[i-1]+si[i],dp[i-2]+adi[i]);
        }
        int s=dp[k]%60,m=(dp[k]/60)%60,h=(dp[k]/3600+8)%24;
        int af=0;
        if(h>12){
            af=1;
            h-=12;
        }
        printf("%02d:%02d:%02d %s\n",h,m,s,af?"pm":"am");
    }
    return 0;
}

hdu1176 免费馅饼

发表于 2020-05-12 分类于算法， ACM

题目大意

也蛮简单的 0时刻人在位置5，位置0-位置10会掉馅饼，人每个时间单位能动一格，动完或者不动之后可以拿到当前位置的馅饼，同一位置同时可能掉多个，问最多拿多少个馅饼

题解

转移方程dp[i][j]=max(dp[i-1][j-1]+pie[i][j],dp[i-1][j]+pie[i][j],dp[i-1][j+1]+pie[i][j]) 简单来说就是从上一个位置移动到下一个位置，加上这个位置能拿的馅饼就完了，实际上这个加法如果极限效率的话是可以提出来的，或者干脆就写到dp里也行，但这样会有一个问题，人在一开始只能是5，要注意在一开始不能从其他位置开始，要限制一下，我为了方便就分开来统计了

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[100020][12],pie[100020][12];
int main(){
    int n;
    while(scanf("%d",&n),n){
        memset(dp,-1,sizeof(dp));
        memset(pie,0,sizeof(pie));
        dp[0][5]=0;
        int mtime=0;
        for(int i=0;i<n;++i){
            int p,t;
            scanf("%d%d",&p,&t);
            mtime=max(mtime,t);
            ++pie[t][p];
        }
        for(int i=1;i<=mtime;++i){
            if(dp[i-1][0]!=-1){
                dp[i][0]=max(dp[i][0],dp[i-1][0]+pie[i][0]);
            }
            if(dp[i-1][1]!=-1){
                dp[i][0]=max(dp[i][0],dp[i-1][1]+pie[i][0]);
            }
            for(int j=1;j<11;++j){
                for(int t=-1;t<2;++t){
                    if(dp[i-1][j+t]!=-1){
                        dp[i][j]=max(dp[i][j],dp[i-1][j+t]+pie[i][j]);
                    }
                }
            }
        }
        int ans=0;
        for(int i=0;i<11;++i){
            ans=max(ans,dp[mtime][i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu1114 Piggy-Bank

发表于 2020-05-11 分类于算法， ACM

显而易见的多重背包。。没啥说的。。直接找最小值就好。。就是初始化时候要初始化最大值，memeset默认按char作为内容来赋值的，所以最大值的设置需要一点点技巧

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=0x3f3f3f3f;
int dp[20020];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(dp,maxn,sizeof(dp));
        int before,after;
        scanf("%d%d",&before,&after);
        int upsum=after-before;
        dp[0]=0;
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            int v,w;
            scanf("%d%d",&v,&w);
            for(int j=0;j<upsum;++j){
                if(dp[j]!=maxn){
                    dp[j+w]=min(dp[j+w],dp[j]+v);
                }
            }
        }
        if(dp[upsum]!=maxn){
            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[upsum]);
        }else{
            printf("This is impossible.\n");
        }
    }
    return 0;
}

hdu1087 Super Jumping! Jumping! Jumping!

发表于 2020-05-10 更新于 2020-05-11 分类于算法， ACM

最长子序列问题的变种，为了求最大和我们就不能一遍遍历二分查找来了。。因为不一定最长的是我们需要的。。所以需要每个地方都试一下才可以

方程dp[i]=dp[i]+max(dp[j])(j<i&&chess[j]<chess[i])

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1020],chess[1020];
int main(){
    int n;
    while(scanf("%d",&n),n){
        memset(dp,0,sizeof(dp));
        memset(chess,0,sizeof(chess));
        for(int i=0;i<n;++i){
            scanf("%d",&chess[i]);
            dp[i]=chess[i];
            for(int j=0;j<i;++j){
                if(chess[j]<chess[i]){
                    dp[i]=max(dp[i],dp[j]+chess[i]);
                }
            }
        }
        int ans=0;
        for(int i=0;i<n;++i){
            ans=max(ans,dp[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu1074 Doing Homework

发表于 2020-05-09 更新于 2020-05-11 分类于算法， ACM

题目大意

你要完成n份作业（n最大15）每份作业有需要完成的时间和时限，不能在要求的时间内完成每晚一个时间单位扣一分，问扣分最少是多少在扣分最少的情况下要求输出完成顺序 要输出所有可能种字典序排的一份

题解

乍一看之下，简单简单~ 不就是按时限排个序就知道最小值了吗唉等等要求输出字典序最小的情况，这就有些意思了因为这时候时限小的可能由于字典序问题不一定排在前面举例来说

math 20 1

se 5 1

这种情况下时限并没有任何意义不能简单排序了之

那要怎么办呢？考虑到n给的很小，我一下子~~之前做过~~想到了状压dp 对于每个状态，搜索置为1的看看能不能从那个状态过来，这样遍历即可由于输入自然的保证了顺序我们只需要搜索时倒着搜索就可以保证字典序了

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<stack>
using namespace std;
struct subject{
    string classname;
    int endtime,lasttime;
};
subject classes[20];
struct node{
    int nowtime,score,lastindex;
}dp[1<<17];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        char tmp[120];
        for(int i=0;i<n;++i){
            scanf("%s%d%d",tmp,&classes[i].endtime,&classes[i].lasttime);
            classes[i].classname=tmp;
        }
        memset(dp,0,sizeof(dp));
        int s=1<<n;
        for(int i=1;i<s;++i){
            dp[i].score=0x3fffffff;
            for(int j=n-1;j>=0;--j){
                int t=1<<j;
                if(i&t){
                    int addscore=dp[i&(~t)].nowtime+classes[j].lasttime-classes[j].endtime;
                    if(addscore<0){
                        addscore=0;
                    }
                    if(dp[i&(~t)].score+addscore<dp[i].score){
                        dp[i].score=dp[i&(~t)].score+addscore;
                        dp[i].nowtime=dp[i&(~t)].nowtime+classes[j].lasttime;
                        dp[i].lastindex=j;
                    }
                }
            }
        }
        stack<string> order;
        int t=(1<<n)-1;
        printf("%d\n",dp[t].score);
        while(t){
            order.push(classes[dp[t].lastindex].classname);
            t&=(~(1<<dp[t].lastindex));
        }
        while(!order.empty()){
            printf("%s\n",order.top().c_str());
            order.pop();
        }
    }
    return 0;
}