题目: http://codevs.cn/problem/2189/
通过增加一维, 将最优性转化为可行性
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- int n,a[30][30];
- bool f[30][30][105];
- int main()
- {
- // memset(f,-2,sizeof f);
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=i;j++)
- {
- scanf("%d",&a[i][j]);
- if(i==n)
- f[i][j][a[i][j]%100]=1;
- }
- for(int i=n-1;i>=1;i--)
- for(int j=1;j<=n;j++)
- for(int k=99;k>0;k--)
- {
- f[i][j][k]=max(f[i+1][j][(k-a[i][j]+100)%100],
- f[i+1][j+1][(k-a[i][j]+100)%100]);
- }
- for(int i=99;i>=0;i--)
- if(f[1][1][i])
- {
- printf("%d",i);
- return 0;
- }
- }
来源: http://www.bubuko.com/infodetail-2522038.html