HDU1565:方格取数(状压DP)

Problem Description
给你一个n*n的格子的棋盘,每个格子里面有一个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。

Input
包括多个测试实例,每个测试实例包括一个整数n 和n*n个非负数(n<=20)

Output
对于每个测试实例,输出可能取得的最大的和

Sample Input
3
75 15 21
75 15 28
34 70 5

Sample Output
188

与HDU1074有点相似,还是用二进制来记录表示取或者不取,一行行的进行计算,用一个数组记录上一行的所有取法,一个数组记录现在这行的所有取法,如果取法进行与运算为1的话,那么就代表有相邻的而不进行计算,然后这样一直DP到最后一行便可以得到最后的结果

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
const int L = 20000;
int n,a[20][20];
int dp[L],tem[L];
int now[L],pre[L];
int ans[L],pre_size,now_size;
 
void dfs(int id,int k,int p,int sum)
{
    if(k>=n)//超过n则可以记录这个状态
    {
        now[++now_size] = p;
        ans[now_size] = sum;
        return ;
    }
    dfs(id,k+2,p|(1<<k),sum+a[id][k]);//这个位置取了,那么就要加上这个位的二进制,通过或运算得出,这个位置取了的话,那么下一个要取的至少要跳两格
    dfs(id,k+1,p,sum);//这个位置不取并跳一格
}
 
void DP()
{
    int i,j,k;
    for(k = 1; k<=n; k++)
    {
        now_size = 0;
        dfs(k,0,0,0);//搜出此行的所有状态
        for(i = 1; i<=now_size; i++)
            dp[i] = 0;
        for(i = 1; i<=now_size; i++)
        {
            for(j = 1; j<=pre_size; j++)
            {
                if(now[i]&pre[j]) continue;//相与为1,证明有相邻而不继续往下
                dp[i] = max(dp[i],tem[j]+ans[i]);
            }
        }
        for(i = 1; i<=now_size; i++)//目前这行的状态保存为上一行
        {
            tem[i] = dp[i];
            pre[i] = now[i];
        }
        pre_size = now_size;
    }
}
 
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i = 1; i<=n; i++)
            for(j = 0; j<n; j++)
                scanf("%d",&a[i][j]);
        tem[1] = pre[1] = 0;//先取一个,但是位置并不确定,
        pre_size = 1;
        DP();
        int ans = 0;
        for(i = 1;i<=pre_size;i++)
        ans = max(ans,tem[i]);
        printf("%d\n",ans);
    }
 
    return 0;
}

 

优美字符串(字符串拼接|java String::endsWith的用法)

优美字符串 描述

对于给定的两个字符串,我们将要做的是将它们拼接起来,拼接成一个“优美”的字符串,那么什么样的字符串是优美的呢?举一个例子,我们要求拼接时,第一个字符串ABCE在前,第二个字符串CEDF在后,拼接的结果是ABCECEDF,接着,我们要对这个ABCECEDF进行修饰,要求将它们在连接处相同的子串重叠在一起,重叠之后的结果为ABCEDF,这就是拼接形成的优美的字符串,现在请你完成这个任务。

输入输入包含两个用空格隔开的字符串s1和s2输出输出一个字符串,表示拼接之后的“优美字符串”样例输入

ABB ABB

样例输出

ABB

提示s1和s2的长度 1≤L≤1000

import java.util.Scanner;
public class Main{
  public static void main(String[] args) {
    Scanner cin=new Scanner(System.in);
    String str1=cin.next(),str2=cin.next();
    int len=str2.length();
    for(;len>0;len--) {
      if(str1.endsWith(str2.substring(0,len))) {
        break;
      }
    }
    System.out.println(str1+str2.substring(len));
    
  }
}

 

SDAU训练日志第33篇(2018年9月26日)

经过了青岛的比赛整个人有点累坏了。最近都在花样补作业,除了看了看比赛题解没怎么做题。

这次比赛让我深深的认识到了和别的学校同级生的差距,自己还是努力的太少了,该水的的课就开始水吧,尽量的调整一下时间分配。昨天下午和教练交流了一下,觉着既然选择了ACM这条路就一路的走下去吧,要做就做最好的那一个,而不是做一个半吊子,那样毫无激情的水着其实一点意思都没有,最后也不会要有什么好的结果,是时候要开始认真起来全身心的投入了。

TO BE THE BEST!

第三届山东省大学生社团节ACM程序设计竞赛感想

这次比赛与其说是写感想,不如说是写检讨,我们17级第一次全体出去比赛结果全军覆没了。我们队本来有希望拿奖的,但是出了交错题的这种低级失误导致了与奖牌失之交臂,不过呢失败乃是成功之母,这次教训惨痛,但是我们也深深的看到了自己的不足之处,希望这是我们转折的契机吧,未来的我们要更加努力。

我们是23号凌晨4点半抵达的青岛,也许是因为我第一次坐火车的缘故,下了车之后就一直有点发烧。大饼的比赛状态好像也不是特别好。。。

比赛是在中午12点20开始的。

上手B题签到题让我A了,唯一的感想就是我的手速太慢了,八九个队伍的手速都比我快。然后第二题和第三题是同时开的,我的是F的多重背包,大饼那个忘了是啥题了,我因为数组开小了,WA了好几次。最后两个题同时出了,瞬间三题排名到了前面,还是蛮兴奋的。然而,接下来就是魔鬼时间了。。我跟晨松开了C,大饼自己研究G和I去了,C题一直没有好的方法,我分了5种情况讨论,推公式,大体思路全出了但是卡在最后一种特殊情况,后来我有点灰心的时候,晨松突然想到了更好的方法,先用1占位进行贪心,我的思路就瞬间开朗了。全队振奋,三个人看着我往上敲代码,之后过了样例,提交。然后在众目睽睽之下他就TLE了,之后进行了各种优化,还是TLE。我们考虑可能是我用的string构造用的时间太长了。然后改字符数组等等,用了N种方法,后来又换了思路,错误是从TLE再到WA再到RT。一个小时过去了。。。

不抱任何希望的时候,大饼突然发现我们交错了题(c交到了I上)。。我们改了一个小时的正确答案,随便找了个代码交上,过了。被气到爆炸,三个人没看到交错了题。。要不然一个小时,应该还能至少再完成一个题。

因为要赶回来的火车再加上比赛推迟了半小时的缘故,我们队提前40分钟离场了。有点遗憾我们的第四个题。但是也是吃一堑长一智吧,以后干什么事都要细心一点!!

比赛前,学长们还给我们加油说要给咱们学校出口气,纵使有了学长的BUFF结果还是打的惨不忍睹,让大家失望了,说到底还是自己不够努力,吸取这次惨痛教训之后好好努力,下次一定为学校争光!

形式主义,面子工程!【持续更新】

某些学校sb领导没事干了整天搞形式主义有毛病吧,有本事你就办点实事!!(真的像某位老师说的,某些老师不整整学生就仿佛失去了存在感)

学校不上课的老师,行政人员占到了全校教师的三分之二,学校每天发着工资就是让你们变着法子玩学生的?这天一个强制活动,隔几天每班派人当强制观众,还天天嫌弃我们太闲了,真是人最怕吃饱了没事干了。

如果真像前几天做的那篇阅读理解上说的,2/3的行政人员,如果有一半的人员能转化到教学岗上,学校的教育也是会突发猛进的。教育才是真正的大头,而这不是靠强制记笔记,强制参加所谓的活动造成的假象。

冬天南校的学生冻死你不管,学校有偷东西的你不管,校外有不法分子试图骚扰女生不管,本部厕所门坏了你不管,宿舍楼和教学楼到现在都喝不上热水你不管(给30块钱打发我们?有本事去装一个啊),课堂笔记形式成风你不管(据说刚开始还因为体育课记笔记闻名全国了)整天就忙些面子工程,真是醉了。

成天截图做面子工程有意思?两天三次截图??

有病吧!忍了一年了,

伪善者比恶者更可恶。我的朋友圈不会被这些玩意玷污的。

 

 

当天下通知?当天交?

 

 

 

 

 

 

最后更新于 2018/12/5

学生信息管理系统(java作业)

作业要求:

定义学生类:
(1)成员变量:学号(String),姓名(String),专业(String)。
(2)构造方法:已知学号,姓名,专业创建学生对象。
(3) 编写获取学生信息的方法public String info(),学生信息格式要求如下: 学号***,姓名***,专业***。
定义学生集合类StudentGroup(用数组实现)。

  • 成员变量:学生数组,学生实际个数size;
  • 构造方法:创建学生数组,长度为100,size初值为0。
  • 编写添加一条学生记录、根据学号修改学生记录、根据学号删除记录、列出所有学生记录、记录按学号排序的五个方法(add,update,delete,query,sort)。功能尽量考虑全面,比如添加记录时学号不能重复,且超过数组长度给出提示不能添加。

继续阅读学生信息管理系统(java作业)