SGU 183 Painting the balls（DP）

- 日理万妓 2022-03-29 08:42 183阅读 0赞

题目链接:[http://acm.sgu.ru/problem.php?contest=0&problem=183][http_acm.sgu.ru_problem.php_contest_0_problem_183]

题意：一行方格，将第i个染色的代价是ci。将其中一些染色，使得任意连续的K个中至少有2个被染色。求最小代价。

思路：f\[i\]\[j\]表示第i个第j个染色的最小代价。

#include <iostream>
    #include <cstdio>
    #include <string.h>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <set>
    #include <stack>
    #include <string>
    #include <map>
    
    
    #define max(x,y) ((x)>(y)?(x):(y))
    #define min(x,y) ((x)<(y)?(x):(y))
    #define abs(x) ((x)>=0?(x):-(x))
    #define i64 long long
    #define u32 unsigned int
    #define u64 unsigned long long
    #define clr(x,y) memset(x,y,sizeof(x))
    #define CLR(x) x.clear()
    #define ph(x) push(x)
    #define pb(x) push_back(x)
    #define Len(x) x.length()
    #define SZ(x) x.size()
    #define PI acos(-1.0)
    #define sqr(x) ((x)*(x))
    
    #define FOR0(i,x) for(i=0;i<x;i++)
    #define FOR1(i,x) for(i=1;i<=x;i++)
    #define FOR(i,a,b) for(i=a;i<=b;i++)
    #define DOW0(i,x) for(i=x;i>=0;i--)
    #define DOW1(i,x) for(i=x;i>=1;i--)
    #define DOW(i,a,b) for(i=a;i>=b;i--)
    using namespace std;
    
    
    void RD(int &x){scanf("%d",&x);}
    void RD(i64 &x){scanf("%I64d",&x);}
    void RD(u32 &x){scanf("%u",&x);}
    void RD(double &x){scanf("%lf",&x);}
    void RD(int &x,int &y){scanf("%d%d",&x,&y);}
    void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}
    void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}
    void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}
    void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
    void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}
    void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}
    void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}
    void RD(char &x){x=getchar();}
    void RD(char *s){scanf("%s",s);}
    void RD(string &s){cin>>s;}
    
    void PR(int x) {printf("%d\n",x);}
    void PR(i64 x) {printf("%I64d\n",x);}
    void PR(u32 x) {printf("%u\n",x);}
    void PR(double x) {printf("%.4lf\n",x);}
    void PR(char x) {printf("%c\n",x);}
    void PR(char *x) {printf("%s\n",x);}
    void PR(string x) {cout<<x<<endl;}
    
    
    const int N=105;
    int n,m,a[10005];
    int f[N][N];
    
    void init(int f[])
    {
        int i;
        for(i=0;i<N;i++) f[i]=1<<30;
    }
    
    int main()
    {
        RD(n,m);
        int i;
        FOR1(i,n) RD(a[i]);
        int j,k;
        for(i=1;i<=m;i++) init(f[i]);
        for(i=1;i<=m;i++) for(j=1;j<i;j++)
        {
            f[i][j]=a[i]+a[j];
        }
        for(i=m+1;i<=n;i++)
        {
            init(f[i%N]);
            for(j=i-m+1;j<i;j++)for(k=i-m;k<j;k++)
            {
                f[i%N][j%N]=min(f[i%N][j%N],f[j%N][k%N]+a[i]);
            }
        }
        int ans=1<<30;
        for(i=n-m+2;i<=n;i++) for(j=n-m+1;j<i;j++)
        {
            ans=min(ans,f[i%N][j%N]);
        }
        PR(ans);
        return 0;
    }

[http_acm.sgu.ru_problem.php_contest_0_problem_183]: http://acm.sgu.ru/problem.php?contest=0&problem=183