[SGU 183]动态规划、优化

【题目大意】给出分给给N个球涂色的代价，让你给某些球涂色，使得满足任意连续M个球中至少有2个是已经涂色的。

【算法分析】易得方程F[I,J]=min(F[J,K])+A[I]   (K

【其它】2WA，一次是瞎扯，根本理解错题意，一次是某个地方i1打成i了。

997585 09.02.10 12:51 edward 183 .CPP Accepted 143 ms 95 kb

【CODE】

#include #include #define min(x,y) (x)<(y)?(x):(y)
#define max(x,y) (x)>(y)?(x):(y)
const int N=11111;
const int M=111;
const int inf=(0x7FFFFFFF-5)/4;
int n,m,a[N],f[M][M],g[M][M],mod;
void init(){
    mod=M;
    memset(f,50,sizeof(f));
    memset(g,50,sizeof(g));
    for (int i=2;i<=m;i++)
      for (int j=1;j        f[i][j]=a[i]+a[j];
    for (int i=2;i<=m;i++){
        g[i][i-1]=f[i][i-1];
        for (int j=i-2;j>=1;j–)
          g[i][j]=min(f[i][j],g[i][j+1]);
    }   
}   

void work(){
    for (int i1=m+1;i1<=n;i1++){
      int i=i1%mod;
      memset(f[i],50,sizeof(f[i]));
      memset(g[i],50,sizeof(g[i]));
      for (int j1=i1-m+1;j1          int j=j1%mod;
          f[i][j]=g[j][(i1-m)%mod]+a[i1];
      }
      g[i][(i1-1)%mod]=f[i][(i1-1)%mod];
      for (int j1=i1-2;j1>=i1-m+1;j1–){
          int j=j1%mod;
          g[i][j]=min(g[i][(j+1)%mod],f[i][j]);
      }   
    }   
}   

void print(){
    int ans=0x7FFFFFFF;
    for (int i=n-m+2;i<=n;i++)
      for (int j=n-m+1;j        if (f[i%mod][j%mod]    printf("%dn",ans);
}   

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (n<=m){
        int min1=0x7FFFFFFF,min2=0x7FFFFFFF;
        for (int i=1;i<=n;i++)
          if (a[i]              min2=min1;
              min1=a[i];
          }
          else
          if (a[i]        printf("%dn",min1+min2);
        return 0;
    }
    init();
    work();
    print();
    return 0;
}