问题2504--建国的签到活动二

2504: 建国的签到活动二

时间限制: 1 Sec  内存限制: 128 MB
提交: 148  解决: 54
[状态] [讨论版] [提交] [命题人:]
题目描述
    建国发现在某宝上即将开始第二波签到活动,这次签到活动会进行n天。这次活动的积分计算方法和上一次活动一样,积分是根据你连续签到的第一天和最后一天计算的。主办方会给你一个积分表,表中会给出所有的a[i][j](a[i][j]表示第i天到第j天全都签过到,且第i-1天与第j+1天没有签到时你可以得到的积分,若不满足所有条件则无法获得该积分)。建国吸取了上一次活动的经验,决定先计划一下自己哪天签到,哪天不签,以便得到更多的积分,你能帮建国计算出他最多可以得到的积分吗?
输入
第一行输入一个正整数n,表示活动的天数。(1 <= n <= 15)
接下来输入n行n列整数,第i行j列表示a[i][j]。(当i>j时,a[i][j]没有实际意义,用-1来表示无意义。当i<=j时,1 <= a[i][j] <= 1000)
输出
输出建国最多可以得到的总积分和可以得到最多积分的方案数,两个整数之间用空格间隔。
样例输入 Copy
5
5 4 3 2 1
-1 4 3 2 1 
-1 -1 3 2 1
-1 -1 -1 2 1
-1 -1 -1 -1 1
样例输出 Copy
9 1
提示
对于样例,第1,3,5天签到时,可以最多得到9积分。只有这一种方案可以得到最多的9积分。
来源/分类