随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.3.3 Home on the Range (DP)
状态转移方程:  dp[i][j] = dp[i][j] && dp[i+1][j] && dp[i][j+1] && dp[i+1][j+1]  , 时间复杂度O(n^3);

/*
ID: lorelei3
TASK: range
LANG: C++
*/

#include <fstream>

using namespace std;

const int MAX = 255;

int n;
bool dp[MAX][MAX];

int main(){
    int i,j,w;
    char ch;
    ifstream fin("range.in");
    ofstream fout("range.out");

    fin>>n;

    for(i=0; i<n; ++i){
        for(j=0; j<n; ++j){
            fin>>ch;
            dp[i][j] = ch-'0';
        }
    }

    for(w=2; w<=n; ++w){
        int cnt = 0;
        for(i=0; i<n; ++i)
            for(j=0; j<n; ++j)
                if(i+w<=n && j+w<=n){
                    dp[i][j] = dp[i][j] && dp[i+1][j] && dp[i][j+1] && dp[i+1][j+1];
                    if(dp[i][j])
                        cnt++;
                }
        if(cnt!=0)
            fout<<w<<" "<<cnt<<endl;
    }
    return 0;
}

posted on 2011-01-13 22:34 小阮 阅读(149) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮