9.29 奶牛练习题

/*bzoj 1613*/
/*暴力5884ms*/
#include<cstdio>
#define maxn 10010
using namespace std;
int n,m,a[maxn],f[maxn][510];
int max(int x,int y){
    return x>y?x:y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            if(j>0)f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);
            if(i-j>=0)for(int k=0;k<=j;k++)f[i][0]=max(f[i][0],f[i-j][k]);
        }
    printf("%d
",f[n][0]);
    return 0;
}
/*简单优化224ms*/
#include<cstdio>
#define maxn 10010
using namespace std;
int n,m,a[maxn],f[maxn][510];
int max(int x,int y){
    return x>y?x:y;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            if(j>0)f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);
            if(i-j>=0)f[i][0]=max(f[i][0],max(f[i-j][j],f[i-1][0]));
        }
    printf("%d
",f[n][0]);
    return 0;
}

/*bzoj 1614 二分*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 1010
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k,num,head[maxn],f[maxn],dis[maxn],l,r,ans;
struct node{
    int v,t,pre;
}e[maxn*20];
queue<int>q;
int init(){
    int x=0;char s=getchar();
    while(s<'0'||s>'9')s=getchar();
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x;
}
void Add(int from,int to,int dis){
    num++;e[num].v=to;
    e[num].t=dis;
    e[num].pre=head[from];
    head[from]=num;
}
bool SPFA(int x){
    for(int i=1;i<=n;i++)dis[i]=inf;
    q.push(1);f[1]=1;dis[1]=0;
    while(!q.empty()){
        int k=q.front();
        q.pop();f[k]=0;
        for(int i=head[k];i;i=e[i].pre){
            int v=e[i].v,cost=0;
            if(e[i].t>x)cost++;
            if(dis[v]>dis[k]+cost){
                dis[v]=dis[k]+cost;
                if(f[v]==0){
                    q.push(v);f[v]=1;
                }
            }
        }
    }
    return dis[n]<=k;
}
int main()
{
    n=init();m=init();k=init();
    int u,v,t;
    for(int i=1;i<=m;i++){
        u=init();v=init();t=init();
        Add(u,v,t);Add(v,u,t);r=max(r,t);
    }
    ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(SPFA(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    printf("%d
",ans);
    return 0;
}

/*bzoj 1609 记忆化*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 30010
using namespace std;
int n,a[maxn],f1[maxn][4],f2[maxn][4];
int Dfs1(int now,int lim){
    if(f1[now][lim]!=-1)return f1[now][lim];
    if(now==n+1)return 0;
    int r=0x7fffffff;
    if(a[now]>=lim)r=min(r,Dfs1(now+1,a[now]));
    r=min(r,Dfs1(now+1,lim)+1);
    return f1[now][lim]=r;
}
int Dfs2(int now,int lim){
    if(f2[now][lim]!=-1)return f2[now][lim];
    if(now==n+1)return 0;
    int r=0x7fffffff;
    if(a[now]<=lim)r=min(r,Dfs2(now+1,a[now]));
    r=min(r,Dfs2(now+1,lim)+1);
    return f2[now][lim]=r;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(f1,-1,sizeof(f1));
    memset(f2,-1,sizeof(f2));
    printf("%d
",min(Dfs1(1,0),Dfs2(1,4)));
}

/*bzoj 1610 模拟*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 210
using namespace std;
int n,x[maxn],y[maxn],ans;
bool f[maxn*10][maxn*10][2];
int Abs(int x){
    return x<0?-x:x;
}
int Gcd(int a,int b){
    return b==0?a:Gcd(b,a%b);
}
void Insert(int a,int b){
    int c=0;
    if(a==0)b=1;
    else if(b==0)a=1;
    else{
        if(a*b<0)c=1;
        int A=Abs(a),B=Abs(b);
        int gcd=Gcd(A,B);
        a=A/gcd;b=B/gcd;
    }
    if(f[a][b][c]==0)ans++;
    f[a][b][c]=1;
}
int main()
{
    //freopen("lines.in","r",stdin);
    //freopen("lines.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            int X=x[i]-x[j];
            int Y=y[i]-y[j];
            Insert(X,Y);
        }
    printf("%d
",ans);
    return 0;
}